Employee Free Time
给一个2d数组, 求所有employee的空闲时间.
这个题, 我用的优先队列解的, 但是code很长, 看了solution后, 觉得解法很巧妙, 而且很通用.
solution用的是线性扫描, 其中的关键理论是: interval之间有几种情况: 半重叠, 完全重叠和分开, 那么前两种可以作为一种, 通过设计一个balance的variable, track两个interval的start和end就可以, 最后只需要找到分开的interval之间的空隙即可.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
/* // 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; } }; |