员工空闲时间
Employee Free Time
题目详情
问题：员工空闲时间
考察：数组、贪心、滑动窗口、栈、二分查找
来源：Citadel
链接：https://www.jointaro.com/interviews/questions/employee-free-time/
We are given a list of employees, each with a list of non-overlapping interval representing their working time. Each employee's working time list is sorted.
Return the list of finite intervals representing common, positive-length free time for all employees.
You may return the result in any 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 [[3,4]].
Example 2:
Input: schedule = [[[1,3],[6,7]],[[2,4]],[[2,5],[9,12]]]
Output: [[5,6],[7,9]]
Constraints:
1 <= schedule.length , schedule[i].length <= 500 <= schedule[i].start < schedule[i].end <= 108
解析
思路：把所有员工忙碌区间合并成一个列表并按开始时间排序，合并重叠区间后，相邻合并区间之间的空隙就是共同空闲时间。也可用小根堆按员工逐路归并。
复杂度：排序解法 O(n log n)，空间 O(n)。