Employee Free Time
Employee Free Time is a hard intervals problem solved with the line sweep pattern.
The best approach, optimal (k-way merge with a min-heap), runs in O(N log k) time and O(k) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from flatten and sort up.
Problem
You are given the working hours of several employees. schedule[i] is the list of busy intervals of employee i; each interval is an Interval object with integer fields start and end, and every employee’s list is sorted and free of overlaps.
Return the list of finite intervals of positive length during which every employee is free, sorted by start time. Time before the earliest busy interval and after the latest one is unbounded, so it is not reported. Intervals that only touch (for example [3, 5] and [5, 7]) leave no free time between them.
Examples
Example 1
- Input
schedule = [[[1, 3], [9, 12]], [[2, 4]], [[6, 8]]]- Output
[[4, 6], [8, 9]]- Why
- Taken together, someone is busy during [1, 4], [6, 8] and [9, 12]. The finite gaps between those blocks are [4, 6] and [8, 9].
Example 2
- Input
schedule = [[[1, 5]], [[3, 10]], [[10, 11]]]- Output
[]- Why
- The busy blocks chain into one block [1, 11] ([3, 10] and [10, 11] touch), so there is no gap of positive length.
Example 3
- Input
schedule = [[[2, 3], [7, 9]], [[5, 6]]]- Output
[[3, 5], [6, 7]]- Why
- Busy blocks [2, 3], [5, 6], [7, 9] leave two finite gaps.
Constraints
1 <= schedule.length <= 501 <= schedule[i].length <= 500 <= schedule[i][j].start < schedule[i][j].end <= 10^8- Each employee's intervals are sorted by start and do not overlap one another.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Flatten and sort | O(N log N) | O(N) |
| Optimal (k-way merge with a min-heap) | O(N log k) | O(k) |
1Flatten and sort
O(N log N)N is the total number of intervals; sorting dominates the single sweep.O(N)The flattened copy of all intervals.Pour every employee's intervals into one list and sort it by start time. Sweep it while tracking the furthest end seen so far: whenever the next interval starts strictly after that end, the stretch between them is a common free interval.
- Collect all intervals into one list and sort by
start. - Set
endto the first interval's end. - For each interval: if
start > end, record[end, start]; thenend = max(end, interval.end). - Return the recorded intervals.
class Solution {
public List<Interval> employeeFreeTime(List<List<Interval>> schedule) {
List<Interval> all = new ArrayList<>();
for (List<Interval> emp : schedule) all.addAll(emp);
all.sort((a, b) -> Integer.compare(a.start, b.start));
List<Interval> free = new ArrayList<>();
int end = all.get(0).end;
for (Interval iv : all) {
if (iv.start > end) free.add(new Interval(end, iv.start));
end = Math.max(end, iv.end);
}
return free;
}
}class Solution:
def employeeFreeTime(self, schedule: List[List['Interval']]) -> List['Interval']:
all_iv = [iv for emp in schedule for iv in emp]
all_iv.sort(key=lambda iv: iv.start)
free = []
end = all_iv[0].end
for iv in all_iv:
if iv.start > end:
free.append(Interval(end, iv.start))
end = max(end, iv.end)
return freeclass Solution {
public:
vector<Interval> employeeFreeTime(vector<vector<Interval>> schedule) {
vector<Interval> all;
for (auto& emp : schedule) for (auto& iv : emp) all.push_back(iv);
stable_sort(all.begin(), all.end(), [](const Interval& a, const Interval& b) { return a.start < b.start; });
vector<Interval> free;
int end = all[0].end;
for (auto& iv : all) {
if (iv.start > end) free.push_back(Interval(end, iv.start));
end = max(end, iv.end);
}
return free;
}
};function employeeFreeTime(schedule) {
const all = [];
for (const emp of schedule) for (const iv of emp) all.push(iv);
all.sort((a, b) => a.start - b.start);
const free = [];
let end = all[0].end;
for (const iv of all) {
if (iv.start > end) free.push(new Interval(end, iv.start));
end = Math.max(end, iv.end);
}
return free;
}2Optimal (k-way merge with a min-heap)
O(N log k)Every one of the N intervals is pushed and popped once on a heap of at most k entries.O(k)The heap holds one entry per employee (output not counted).Each employee's list is already sorted, so the next interval in global start order is always the head of one of the k lists. Keep one pointer per employee in a min-heap keyed by start time and sweep exactly as before, without sorting all N intervals.
- Push
(start, employee, 0)for every employee. - Pop the smallest; if a previous
endexists and this start is greater, record[end, start]. - Update
end = max(end, interval.end)and push the same employee's next interval, if any. - Repeat until the heap is empty.
class Solution {
public List<Interval> employeeFreeTime(List<List<Interval>> schedule) {
PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
for (int e = 0; e < schedule.size(); e++) {
if (!schedule.get(e).isEmpty()) heap.add(new int[] { schedule.get(e).get(0).start, e, 0 });
}
List<Interval> free = new ArrayList<>();
int end = -1;
while (!heap.isEmpty()) {
int[] top = heap.poll();
Interval iv = schedule.get(top[1]).get(top[2]);
if (end >= 0 && iv.start > end) free.add(new Interval(end, iv.start));
end = Math.max(end, iv.end);
int next = top[2] + 1;
if (next < schedule.get(top[1]).size()) heap.add(new int[] { schedule.get(top[1]).get(next).start, top[1], next });
}
return free;
}
}class Solution:
def employeeFreeTime(self, schedule: List[List['Interval']]) -> List['Interval']:
heap = [(emp[0].start, e, 0) for e, emp in enumerate(schedule) if emp]
heapq.heapify(heap)
free = []
end = -1
while heap:
_, e, i = heapq.heappop(heap)
iv = schedule[e][i]
if end >= 0 and iv.start > end:
free.append(Interval(end, iv.start))
end = max(end, iv.end)
if i + 1 < len(schedule[e]):
heapq.heappush(heap, (schedule[e][i + 1].start, e, i + 1))
return freeclass Solution {
public:
vector<Interval> employeeFreeTime(vector<vector<Interval>> schedule) {
priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> heap;
for (int e = 0; e < (int)schedule.size(); e++) {
if (!schedule[e].empty()) heap.push({schedule[e][0].start, e, 0});
}
vector<Interval> free;
int end = -1;
while (!heap.empty()) {
auto [s, e, i] = heap.top(); heap.pop();
Interval iv = schedule[e][i];
if (end >= 0 && iv.start > end) free.push_back(Interval(end, iv.start));
end = max(end, iv.end);
if (i + 1 < (int)schedule[e].size()) heap.push({schedule[e][i + 1].start, e, i + 1});
}
return free;
}
};class MinHeap {
constructor(cmp = (a, b) => a - b) { this.a = []; this.cmp = cmp; }
size() { return this.a.length; }
isEmpty() { return this.a.length === 0; }
push(x) {
const a = this.a;
a.push(x);
let i = a.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (this.cmp(a[i], a[p]) >= 0) break;
[a[i], a[p]] = [a[p], a[i]];
i = p;
}
}
pop() {
const a = this.a, top = a[0], last = a.pop();
if (a.length > 0) {
a[0] = last;
let i = 0;
while (true) {
const l = 2 * i + 1, r = l + 1;
let m = i;
if (l < a.length && this.cmp(a[l], a[m]) < 0) m = l;
if (r < a.length && this.cmp(a[r], a[m]) < 0) m = r;
if (m === i) break;
[a[i], a[m]] = [a[m], a[i]];
i = m;
}
}
return top;
}
}
function employeeFreeTime(schedule) {
const heap = new MinHeap((a, b) => a[0] - b[0]);
for (let e = 0; e < schedule.length; e++) {
if (schedule[e].length > 0) heap.push([schedule[e][0].start, e, 0]);
}
const free = [];
let end = -1;
while (!heap.isEmpty()) {
const [, e, i] = heap.pop();
const iv = schedule[e][i];
if (end >= 0 && iv.start > end) free.push(new Interval(end, iv.start));
end = Math.max(end, iv.end);
if (i + 1 < schedule[e].length) heap.push([schedule[e][i + 1].start, e, i + 1]);
}
return free;
}Edge cases to test
- A single employee with a single interval (no free time)
- Intervals from different employees that only touch at an endpoint (no gap there)
- One long interval covering everyone else's intervals
- Employees whose schedules interleave
Hints
Hint 1
Free time for everyone means time when nobody is busy. Only the union of all busy intervals matters, not who owns them.
Hint 2
Sort every interval by start and merge them as in merging intervals; the gaps between consecutive merged blocks are the answer.
Hint 3
Each employee's list is already sorted, so you can merge the k lists with a min-heap instead of sorting everything from scratch.
FAQ
What is the best time complexity for Employee Free Time?
Optimal (k-way merge with a min-heap) runs in O(N log k) time and O(k) extra space. Every one of the N intervals is pushed and popped once on a heap of at most k entries.
Which pattern does Employee Free Time use?
It is a intervals problem that uses the line sweep pattern. Other problems with the same pattern: Meeting Rooms II, Car Pooling, Divide Intervals Into Minimum Number of Groups.
Is there a brute force solution for Employee Free Time?
Yes. Flatten and sort takes O(N log N) time and O(N) space. Pour every employee's intervals into one list and sort it by start time.
Which edge cases should I test for Employee Free Time?
A single employee with a single interval (no free time); Intervals from different employees that only touch at an endpoint (no gap there); One long interval covering everyone else's intervals; Employees whose schedules interleave.