759. Employee Free Time

• 方法1: sweep line

We are given a list schedule of employees, which represents the working time for each employee.

Each employee has a list of non-overlapping Intervals, and these intervals are in sorted order.

Return the list of finite intervals representing common, positive-length free time for all employees, also in sorted order.

Example 1:

Input: schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]]
Output: [[3,4]]
Explanation:
There are a total of three employees, and all common
free time intervals would be [-inf, 1], [3, 4], [10, inf].
We discard any intervals that contain inf as they aren't finite.
           

Example 2:

Input: schedule = [[[1,3],[6,7]],[[2,4]],[[2,5],[9,12]]]
Output: [[5,6],[7,9]]
           

(Even though we are representing Intervals in the form [x, y], the objects inside are Intervals, not lists or arrays. For example, schedule[0][0].start = 1, schedule[0][0].end = 2, and schedule[0][0][0] is not defined.)

Also, we wouldn’t include intervals like [5, 5] in our answer, as they have zero length.

Note:

schedule and schedule[i] are lists with lengths in range [1, 50].

0 <= schedule[i].start < schedule[i].end <= 10^8.

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

方法1: sweep line

思路：

将所有event時間點都排序，并且記住是start還是end。每次取出最早的event，根據type做如下操作：

1. start： count++，如果count從0變成1，标志着一段free time的終止，組成區間送入結果。
2. end：count–，如果count 從1 變成0，标志着一段free time的開始，記住這個開始。

struct cmp {
    bool operator()(const pair<int, bool> & a, const pair<int, bool> & b) const {
        if (a.first == b.first) return a.second;
        return a.first < b.first;
    } 
};

class Solution {
public:
    vector<vector<int>> employeeFreeTime(vector<vector<vector<int>>>& schedule) {
        
        multiset<pair<int, bool>, cmp> events;
        for (auto sch: schedule) {
            for (auto v: sch) {
                events.insert({v[0], true});
                events.insert({v[1], false});
            }
        }
        
        int count = 0; 
        int start = INT_MIN;
        int end = INT_MIN;
        vector<vector<int>> result;
        for (auto e: events) {
            // start 
            if (e.second == true) {
                if (!count && start != INT_MIN){
                    end = e.first;
                    result.push_back({start, end});
                }
                count++;
            }
            else {
                if (count == 1) {
                    start = e.first;
                }
                count --;
            }
        }
        return result;
    }
};