Employee Free Time

给一个2d数组, 求所有employee的空闲时间.

这个题, 我用的优先队列解的, 但是code很长, 看了solution后, 觉得解法很巧妙, 而且很通用.

solution用的是线性扫描, 其中的关键理论是: interval之间有几种情况: 半重叠, 完全重叠和分开, 那么前两种可以作为一种, 通过设计一个balance的variable, track两个interval的start和end就可以, 最后只需要找到分开的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) {
        int open = 0;
        int close = 1;
        vector<pair<int, int>> events;
        for(auto s : schedule) {
            for(auto i : s) {
                events.push_back({i.start, open});
                events.push_back({i.end, close});
            }
        }
        vector<Interval> res;
        sort(events.begin(), events.end());
        int pre = -1;
        int balance = 0;
        for(auto e : events) {
            if(balance == 0 && pre >= 0) {
                res.push_back(Interval(pre, e.first));
            }
            if(e.second == 0) {
                balance++;
            }
            else {
                balance--;
            }
            pre = e.first;
        }
        return res;
    }
};