Employee Free Time
LWC 66: 759. Employee Free Time
Problem:
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.
Example 1:
Input: schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]] Output: [[3,4]] Explanation: There are a total of three employees, and all common free time intervals would be [-inf, 1], [3, 4], [10, inf]. We discard any intervals that contain inf as they aren’t finite.
Example 2:
Input: schedule = [[[1,3],[6,7]],[[2,4]],[[2,5],[9,12]]] Output: [[5,6],[7,9]] (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.
Note:
- schedule and schedule[i] are lists with lengths in range [1, 50].
- 0 <= schedule[i].start < schedule[i].end <= 10^8.
思路： 大致题意是求所有区间的并集的补集。先根据区间的start排序，假设当前区间为now，那么如果新来的区间start在now区间表示的范围内，说明两个区间存在交集，更新右边界，直到不存在交集时，能够求得第一个补集，依此类推。
Java版本：
class P implements Comparable<P>{
int start;
int end;
P(int start, int end){
this.start = start;
this.end = end;
}
@Override
public int compareTo(P o) {
return this.start == o.start ? this.end - o.end : this.start - o.start;
}
@Override
public String toString() {
return "[" + start + ", " + end + "]";
}
}
public List<Interval> employeeFreeTime(List<List<Interval>> avails) {
List<P> unSorted = new ArrayList<>();
for (List<Interval> avail : avails) {
for (Interval inter : avail) {
unSorted.add(new P(inter.start, inter.end));
}
}
Collections.sort(unSorted);
List<Interval> ans = new ArrayList<>();
int n = unSorted.size();
for (int i = 0; i < n; ++i) {
P now = unSorted.get(i);
int maxRight = now.end;
i ++;
while (i < n && unSorted.get(i).start <= maxRight) {
maxRight = Math.max(maxRight, unSorted.get(i).end);
i ++;
}
if (i < n) ans.add(new Interval(maxRight, unSorted.get(i).start));
i --;
}
return ans;
}Python版本：
# Definition for an interval.
# class Interval(object):
# def __init__(self, s=0, e=0):
# self.start = s
# self.end = e
class Solution(object):
def employeeFreeTime(self, avails):
"""
:type schedule: List[List[Interval]]
:rtype: List[Interval]
"""
from itertools import chain
avails = list(sorted(chain(*avails), key = lambda Interval : Interval.start))
ans = list()
n = len(avails)
i = 0
while (i < n):
now = avails[i]
maxRight = now.end
j = i + 1
while (j < n and avails[j].start <= maxRight):
maxRight = max(maxRight, avails[j].end)
j += 1
i = j - 1
if j < n: ans.append(Interval(maxRight, avails[j].start))
i += 1
return ans