Employee Free Time

Hard Intervals Line Sweep Original on LeetCode

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 <= 50
  • 1 <= schedule[i].length <= 50
  • 0 <= 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.

00:00
Testcase

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.

ApproachTimeSpace
Flatten and sortO(N log N)O(N)
Optimal (k-way merge with a min-heap)O(N log k)O(k)

1Flatten and sort

TimeO(N log N)N is the total number of intervals; sorting dominates the single sweep.
SpaceO(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.

  1. Collect all intervals into one list and sort by start.
  2. Set end to the first interval's end.
  3. For each interval: if start > end, record [end, start]; then end = max(end, interval.end).
  4. 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;
    }
}

2Optimal (k-way merge with a min-heap)

TimeO(N log k)Every one of the N intervals is pushed and popped once on a heap of at most k entries.
SpaceO(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.

  1. Push (start, employee, 0) for every employee.
  2. Pop the smallest; if a previous end exists and this start is greater, record [end, start].
  3. Update end = max(end, interval.end) and push the same employee's next interval, if any.
  4. 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;
    }
}

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.