1 题目
We are given a list
schedule
of employees, which represents the working time for each employee.
Each employee has a list of non-overlapping
Intervals
, and these intervals are in sorted order.
Return the list of finite intervals representing common, positive-length free time for all employees, also in sorted order.
(Even though we are representing
Intervals
in the form
[x, y]
, the objects inside are
Intervals
, not lists or arrays. For example,
schedule[0][0].start = 1
,
schedule[0][0].end = 2
, and
schedule[0][0][0]
is not defined). Also, we wouldn't include intervals like [5, 5] in our answer, as they have zero length.
2 尝试解
2.1 分析
给定一组工人的上班时间组成的向量,每个元素是该工人的工作时间区间组成的向量。求所有人的公共空闲时间区间向量。
简单的区间合并,如果两个区间有公共区域,则合并两个区间。具体算法为,先将二维向量展开,然后用最小堆按照起始时间对区间排序得到Intervals,设当前结束时间为end,初始值为Intervals.top().end。
如果Intevals.top().start <= end,说明堆顶区间与之前的区间有重叠部分或者无缝衔接,可以合并,即删去堆顶元素,并且更新end,考虑到堆顶元素的结束时间不一定比当前结束时间早,所以更新规则为end = max(end, Intervals.top().end)。
如果Intervals.top().start > end,说明在堆顶区间开始之前,有空余时间,该时间区间为(end,Intervals.top().start),加入到结果中。再删去堆顶元素,并且更新end。
2.2 代码
class Solution {
public:
struct cmp{
bool operator()(Interval&A,Interval&B){
return A.start > B.start;
}
};
vector<Interval> employeeFreeTime(vector<vector<Interval>> schedule) {
vector<Interval> result;
priority_queue<Interval,vector<Interval>,cmp> saver;
for(auto person:schedule){
for(auto interval:person){
saver.push(interval);
}
}
int end = saver.top().start;
while(saver.size()){
if(saver.top().start > end){
result.push_back(Interval(end,saver.top().start));
}
end = max(end,saver.top().end);
saver.pop();
}
return result;
}
};
3 标准解
3.1 分析
考虑一个时间轴t,对于每一个时间区间interval,在t = interval.start时,balance++,在t = interval.end时,balance--。那么balance = 0的时刻即为空闲时间。
3.2 代码
class Solution {
public:
vector<Interval> employeeFreeTime(vector<vector<Interval>>& a) {
vector<Interval> res;
map<int, int> timeline;
for (int i = 0; i < a.size(); i++) {
for (int j = 0; j < a[i].size(); j++) {
timeline[a[i][j].start]++;
timeline[a[i][j].end]--;
}
}
int workers = 0;
for (pair<int, int> p : timeline) {
workers += p.second;
if (!workers) res.push_back(Interval(p.first, 0));
if (workers && !res.empty() && !res.back().end) res.back().end = p.first;
}
if (!res.empty()) res.pop_back();
return res;
}
};