We are given a listscheduleof employees, which represents the working time for each employee.
Each employee has a list of non-overlappingIntervals, 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.
(Even though we are representingIntervalsin the form[x, y], the objects inside areIntervals, not lists or arrays. For example,schedule[0][0].start = 1, schedule[0][0].end = 2, andschedule[0][0][0]is not defined.)
Also, we wouldn't include intervals like [5, 5] in our answer, as they have zero length.
Note:
scheduleandschedule[i]are lists with lengths in range[1, 50].
0 <= schedule[i].start < schedule[i].end <= 10^8.
2. Implementation
(1) Heap
/**
* Definition for an interval.
* public class Interval {
* int start;
* int end;
* Interval() { start = 0; end = 0; }
* Interval(int s, int e) { start = s; end = e; }
* }
*/
class Solution {
public List<Interval> employeeFreeTime(List<List<Interval>> schedule) {
List<Interval> res = new ArrayList<>();
if (schedule == null || schedule.size() == 0) {
return res;
}
List<Interval> list = new ArrayList<>();
for (List<Interval> time : schedule) {
for (Interval interval : time) {
list.add(interval);
}
}
Collections.sort(list, new Comparator<Interval>() {
@Override
public int compare(Interval i1, Interval i2) {
return i1.start == i2.start ? i1.end - i2.end : i1.start - i2.start;
}
});
PriorityQueue<Integer> endTime = new PriorityQueue<>(Collections.reverseOrder());
endTime.add(list.get(0).end);
for (int i = 1; i < list.size(); i++) {
if (endTime.size() > 0 && endTime.peek() < list.get(i).start) {
res.add(new Interval(endTime.peek(), list.get(i).start));
}
endTime.add(list.get(i).end);
}
return res;
}
}