leetcode：759. 员工空闲时间（会员题）
lintcode：[困难] 850 · 员工空闲时间

题目

我们得到一个员工的 schedule 列表,代表每个员工工作时间。
每个员工有一个不重合时段的列表 Intervals，这些时段按序排列。
返回一个所有员工共有的空闲时段的列表，并按序排列。
我们的 Intervals 是一个一维数组，其中每两个数表示一个区间，即 [1,2,8,10] 表示这个员工的工作时间是 [1,2] 和 [8,10]。
并且，我们的答案不会包括像 [5,5] 这样的，因为它们的长度是 0。

schedule 和 schedule[i] 为长度范围在 [1, 100] 的列表。
0 <= schedule[i].start < schedule[i].end <= 10^8。

示例：

输入：schedule = [[1,2,5,6],[1,3],[4,10]]
输出：[(3,4)]
解释：共有三个员工,并且所有员工共有的空闲时段是[-inf, 1], [3, 4], [10, inf]。去除掉包含inf的答案。

输入：schedule = [[1,3,6,7],[2,4],[2,5,9,12]]
输出：[(5,6),(7,9)]
解释：共有三个员工,并且所有员工共有的空闲时段是[-inf, 1], [5, 6], [7, 9],[12,inf]。去除掉包含inf的答案。

解答 & 代码

排序：所有工作时间区间按起始时间升序排序（下面的代码还按结束时间降序排序，实际可以不用管结束时间）

初始 end = 第一个区间的结束时间，遍历后续区间

分析区间的三种情况：覆盖、相交、无交集
1. 覆盖：跳过
2. 相交：end 变为当前区间结束时间
3. 无交集：不相交区域就是公共空闲时间，存入结果数组；end 变为当前区间结束时间

/**
 * Definition of Interval:
 * class Interval {
 * public:
 *     int start, end;
 *     Interval(int start, int end) {
 *         this->start = start;
 *         this->end = end;
 *     }
 * }
 */

class Solution {
private:
    // 按开始时间升序、结束时间降序排序
    static bool cmp(vector<int>& inter1, vector<int>& inter2)
    {
        return inter1[0] < inter2[0] || (inter1[0] == inter2[0] && inter1[1] > inter2[1]);
    }
public:
    /**
     * @param schedule: a list schedule of employees
     * @return: Return a list of finite intervals 
     */
    vector<Interval> employeeFreeTime(vector<vector<int>> &schedule) {
        vector<vector<int>> intervalList;
        for(int i = 0; i < schedule.size(); ++i)
        {
            for(int j = 0; j < schedule[i].size(); j += 2)
                intervalList.push_back(vector<int>{schedule[i][j], schedule[i][j + 1]});
        }

        // 将所有工作时间区间按开始时间升序排序
        sort(intervalList.begin(), intervalList.end(), cmp);
        vector<Interval> result;
        int end = intervalList[0][1];    // end 初始化为第 0 个区间的结束时间
        // 遍历区间
        for(int i = 1; i < intervalList.size(); ++i)
        {
            // 覆盖：跳过当前区间
            if(intervalList[i][1] <= end)
                continue;
            // 相交：end 变为当前区间结束时间
            else if(intervalList[i][0] <= end && intervalList[i][1] > end)
                end = intervalList[i][1];
            // 无交集：不相交区域是公共空闲时间，存入结果数组。end 变为当前区间结束时间
            else if(intervalList[i][0] > end)
            {
                Interval empty(end, intervalList[i][0]);
                result.push_back(empty);
                end = intervalList[i][1];
            }
        }
        return result;
    }
};

复杂度分析：设所有员工的工作时间区间总数位 n

时间复杂度 O(nlogn)：排序时间复杂度
空间复杂度 O(n)：intervalList 数组存储了所有员工的所有工作区间

执行结果：

执行结果：通过

执行用时：41 ms, 在所有 C++ 提交中击败了 88.10% 的用户
内存消耗：2.8 MB, 在所有 C++ 提交中击败了 88.10% 的用户

hot 100

[困难] 759. 员工空闲时间

题目

解答 & 代码