759 Employee Free Time
759. Employee Free Time
1. Question
We are given a listschedule
of 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.
Example 2:
Input: schedule = [[[1,3],[6,7]],[[2,4]],[[2,5],[9,12]]]
Output: [[5,6],[7,9]]
(Even though we are representingIntervals
in 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:
schedule
andschedule[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;
}
}
3. Time & Space Complexity
Heap: 时间复杂度O(nlogn), n为所有employee的工作时间段,空间复杂度O(n)
Last updated
Was this helpful?