# 759 - Employee Free Time

解法一 - 找到沒有 overlap 的部分，存入 res

在這題之前的題目，我們都著重在找 overlap 的地方，而這題剛好是要找不 overlap 的地方。另外這題有個迷惑人心的地方，就是把 interval 拆給很多個 employee，但其實我們可以把所有的 interval 都一起考慮，畢竟我們是要找所有人共通的 free time。

當我們把所有的 interval 都放到一起後，我們可以把從第一個 interval 開始看，然後不斷跟後面的比較，這時就分成三種情況，可以列舉如下：

列舉完之後，邏輯就變得簡單很多，我們實作如下：

/*
// Definition for an Interval.
class Interval {
public:
    int start;
    int end;

    Interval() {}

    Interval(int _start, int _end) {
        start = _start;
        end = _end;
    }
};
*/
class Solution {
public:
    vector<Interval*> employeeFreeTime(vector<vector<Interval*>> schedule) {
        // Put all intervals together
        vector<Interval*> intervals;
        for(auto& emp: schedule) {
            for(auto& interv: emp) {
                intervals.push_back(interv);
            }
        }

        // Sort all intervals by start time
        sort(intervals.begin(), intervals.end(), []
             (const Interval* a, const Interval* b) {
                 return a->start < b->start;
        });

        // Start finding free time
        vector<Interval*> res;
        Interval* cur = intervals[0];
        for(int i = 1; i < intervals.size(); ++i) {
            Interval* next = intervals[i];

            // no overlap, add free time
            if(cur->end < next->start) {
                res.push_back(new Interval(cur->end, next->start));
                cur = next;
            }
            else {
                cur = (cur->end < next->end) ? next : cur;
            }
        }

        return res;
    }
};