本质是merge intervals, merge完后, intervals间的空隙就是答案. 如何merge? 要么sort, 要么用PQ. 还有一个好方法就是sweep-line algo.
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
| class Solution {
public List<Interval> employeeFreeTime(List<List<Interval>> schedule) {
TreeMap<Integer, Integer> timeScoresMap = new TreeMap<>();
for (List<Interval> intervals : schedule) {
for (Interval interval : intervals) {
timeScoresMap.put(interval.start, timeScoresMap.getOrDefault(interval.start, 0) + 1);
timeScoresMap.put(interval.end, timeScoresMap.getOrDefault(interval.end, 0) - 1);
}
}
int start = -1, scores = 0;
List<Interval> ans = new ArrayList<>();
for (int time : timeScoresMap.keySet()) {
scores += timeScoresMap.get(time);
if (scores == 0 && start == -1) {
start = time;
} else if (scores > 0 && start != -1) {
ans.add(new Interval(start, time));
start = -1;
}
}
return ans;
}
}
|
这个方法很妙. 这个algo叫做sweep-line algorithm. 我们这样规定: 到达一个interval的开端, 我们让score + 1, 到达一个interval的末端我们让interval - 1. 因为interval的开端总是小于等于interval的末端, 我们在任何时刻的score都是大于等于0的. 如果某个时刻的score小于0, 代表我们经历过的start小于经历过的end, 这是不可能的. 那么score等于0意味着什么呢? 意味着我们在某个时刻经历完了之前所有intervals, 在这个题里面表示干完了之前所有的活. 如果某个时刻的score等于0, 那就说明此时就是休息的开始. 那么到什么时候会停止呢? 直到在某个时刻score大于0了, 此时就是休息的结束. 上面的start标记着休息的开始. 之所以一开始让start等于-1是因为, 题目不允许负无穷到某个开始时刻去休息. 如果题目改成下届是0, 此时比如说所有的intervals最早也是在1时刻开始, 那么我们可以在[0, 1]这个时间段休息. 但是这道题不是, 于是一开始认为没有休息时间. 当某个时刻score == 0时, 此时就是休息的开始, 我们让start = time. 如果在某个时刻, score大于0且start不为0, 这表示休息的结束, 我们添加这段休息时间到ans中, 然后让start = -1. 如果此时start不等于-1, 我们之后遇到score大于0时会无法区分我们是在工作时刻还是在休息结束时刻.
时间复杂度: O(nlogn) 因为用了treemap(log1 + log2 + log3 + … + logn收敛于nlogn)
空间复杂度: O(n) 一样还是用了treemap存n个intervals.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public List<Interval> employeeFreeTime(List<List<Interval>> schedule) {
PriorityQueue<Interval> pq = new PriorityQueue<>((a, b) -> a.start - b.start);
schedule.forEach(e -> pq.addAll(e));
List<Interval> ans = new ArrayList<>();
int freeTimeStart = pq.peek().end;
while (!pq.isEmpty()) {
if (pq.peek().start <= freeTimeStart) {
freeTimeStart = Math.max(freeTimeStart, pq.peek().end);
} else {
ans.add(new Interval(freeTimeStart, pq.peek().start));
freeTimeStart = pq.peek().end;
}
pq.poll();
}
return ans;
}
}
|
其实不用管多少个员工之类的. 要的是所有的员工都能休息, 那就是在某个时间段大家都不工作, 如果都不工作, 给的这些intervals该merge的merge剩下的intervals就是空闲的时间. 感觉不太对劲? 反证法. 假设某个休息时刻是intervals merge完后不在剩下的intervals中. 那么必然在那些merge好的intervals中, 但是这些时刻至少有一个employee在工作, 因此休息时刻不可能出现在merge好的intervals中. 这证明了休息的intervals只可能出现在merge后剩余的空白intervals中. 那如果剩下的intervals可能不全是可以用来休息的. 假设有个interval它不能用来休息, 也就是有员工工作, 但是此时并没有员工的interval出现在这个空白区域, 于是不满足我们的假设. 综上merge好intervals剩下的空白intervals就是休息时刻.
具体怎么写码呢? 牵扯到merge intervals, 自然而然想到根据interval的start来sort一下. 于是想到了用PQ. 当然我们用个list把intervals都装里面然后最后直接sort一下也行. 时间复杂度都是O(nlogn). 然后我们假设pq顶部的end时间就是休息的开始. 如果后续有intervals和顶部的这个interval有交集, 那么我们就让end时间等于二者end的最大值. 只要有交集, end就不断更新, 直到某个interval的start大于这个end, 此时就可以休息, 休息时间段就是[此时的end, pq顶部的interval的start]. 休息好后, 然后我们把end重新设置为pq顶部的end, 继续这个merge的操作.
时间复杂度: O(nlogn)
空间复杂度: O(n) 因为把所有的intervals都装到了pq中.
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
| class Solution {
public List<Interval> employeeFreeTime(List<List<Interval>> schedule) {
PriorityQueue<Pair<Integer, Integer>> pq = new PriorityQueue<>(
(a, b) -> schedule.get(a.getKey()).get(a.getValue()).start
- schedule.get(b.getKey()).get(b.getValue()).start);
for (int i = 0; i < schedule.size(); i++) {
pq.offer(new Pair<>(i, 0));
}
int freeTimeStart = schedule.get(pq.peek().getKey()).get(pq.peek().getValue()).end;
List<Interval> ans = new ArrayList<>();
while (!pq.isEmpty()) {
Pair<Integer, Integer> earliestStartPair = pq.peek();
Interval earliestStartInterval = schedule.get(earliestStartPair.getKey()).get(earliestStartPair.getValue());
if (earliestStartInterval.start > freeTimeStart) {
ans.add(new Interval(freeTimeStart, earliestStartInterval.start));
}
int workTimeEnd = earliestStartInterval.end;
while (!pq.isEmpty() && schedule.get(pq.peek().getKey()).get(pq.peek().getValue()).start <= workTimeEnd) {
Pair<Integer, Integer> currPair = pq.poll();
workTimeEnd = Math.max(workTimeEnd, schedule.get(currPair.getKey()).get(currPair.getValue()).end);
if (currPair.getValue() + 1 < schedule.get(currPair.getKey()).size()) {
pq.offer(new Pair<>(currPair.getKey(), currPair.getValue() + 1));
}
}
freeTimeStart = workTimeEnd;
}
return ans;
}
}
|
我们有个条件没有用到, 就是每个员工的工作时间是sort好的. 那么我们可以先添加K个intervals到pq中, 然后merge的过程还是一样. 只不过我们pop出一个interval后, 我们要把该员工后续的下一个interval放到pq中去. 如果后面没有就不放了. 这样我们也是按照interval的start从小到大来进行merge的.
本质就是按照interval的start排序, 从小到大来进行遍历. 我们这个approach也能保证从小到大遍历.
这样时间复杂度就变到了O(nlogk), 因为pq中最大就是k个元素.
空间复杂度变为: O(k)
但实际运行没有第二个步骤快.
这个想法是受到merge K lists/arrays. 只要牵扯到k个的, 第一时间想到PQ哈哈哈哈哈.
