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;
}
};