给一堆可能有overlap的interval, 让返回没有overlap的interval的间隔。相当于把所有有overlap的interval合并，然后把不能合并的返回。既可以用merge interval的方法不断用跟当前Interval有交集的interval扩张end，也可以用meeting roomII的方法用+1-1扫描线。扫描线的话当sum为0时表示所有与前面start对应end都遇到了，此时就是gap开始。gap结束的位置即下一个interval的start位置。因为不考虑最后一个Interval和无穷的gap，所以要把最后一个gap退掉。TreeMap会根据key自动排好序。
/*
* @lc app=leetcode id=759 lang=cpp
*
* [759] Employee Free Time
*
*
*/
class Solution {
public:
vector<Interval> employeeFreeTime(vector<vector<Interval>>& schedule) {
vector<Interval> res;
map<int, int> m;
for (const auto &s : schedule) {
for (const auto &i : s) {
++m[i.start];
--m[i.end];
}
}
int sum = 0;
for (const auto &p : m) {
sum += p.second;
if (sum == 0) res.push_back(Interval(p.first, -1));
else if (!res.empty() && res.back().end == -1) res.back().end = p.first;
}
if (!res.empty()) res.pop_back();
return res;
}
};