← DSA Atlas
Dedicated problem page · #759

Employee Free Time

HardIntervals and Sweep LineFlatten, sort, find gapsMerge intervals across all employees, emit the holes
Solve on LeetCode ↗
759
HardIntervals and Sweep LineMerge intervals across all employees, emit the holesFlatten, sort, find gaps

Employee Free Time

Each employee has a list of non-overlapping, sorted working Intervals. Return the list of finite intervals of positive length that are common free time for ALL employees, sorted in order. Do not include the unbounded time before everyone starts or after everyone ends.

Open official problem prompt ↗
In plain English

Find every finite stretch of time during which no employee anywhere is working.

Picture it like this

Overlay everyone's calendars onto one shared calendar and shade in every busy block. The clear stripes between shaded blocks are the moments the whole company is simultaneously free.

Example
Input
schedule = [[[1,2],[5,6]], [[1,3]], [[4,10]]]
Output
[[3, 4]]
Why
Merging all busy intervals gives [1,3] and [4,10]; the only gap between them is [3,4], when everyone is free.
Constraints
1 <= schedule.length, schedule[i].length <= 500 <= Interval.start < Interval.end <= 10^8Intervals within each employee are disjoint and sorted
Pattern lesson

See the pattern, then code

Flatten, sort, find gaps
Recognition clue

Common free time = the complement of the union of everyone's busy intervals. Merging many pre-sorted interval lists and reporting the gaps is the giveaway.

↗
Intervals and Sweep Line

Meetings, schedules, overlapping ranges, resource allocation, or timeline events.. Whether an interval belongs to employee A or B is irrelevant to when SOMEONE is busy. Pool every interval, sort by start, sweep once merging overlaps, and each gap between the running merged block and the next interval is a shared free window.

New words, made simpleKnow these before the algorithm
Free time
A positive-length interval where zero employees are busy
Union of intervals
The merged coverage of all busy periods regardless of who owns them
Gap
Space between the end of one merged block and the start of the next
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
K-way merge with a heap

Asymptotically tighter and elegant, but heavier to implement than a flat sort for the small constraints here.

Since each employee's list is already sorted, merge them with a min-heap and detect gaps during the merge.

Time O(n log k)Space O(k)
Best choiceFlatten, sort, sweep

Simple and fast enough given n <= 2500; the clearest correct approach.

Concatenate all intervals, sort by start, and merge in one pass emitting the holes.

Time O(n log n)Space O(n)
The rule we keep true

Invariant

prev_end always equals the rightmost end among all intervals seen so far that belong to the current contiguous busy block.

Why this is correct

Reasoning

Sorting by start guarantees intervals are processed left to right. If the next interval starts at or before prev_end it overlaps the current busy block and only possibly extends it. If it starts strictly after prev_end, no interval covers (prev_end, next.start), so that span is free for everyone; recording it and then resetting coverage to the new interval captures exactly the complement of the union.

The algorithm in three movesSay these aloud before coding
1Flatten all employees' intervals into one list

sorted starts: [1,2],[1,3],[4,10],[5,6]

2Sort the list by start

prev_end=3, next start 4 > 3 -> free [3,4]

3Sweep, tracking the farthest end covered so far

prev_end becomes 10

4When the next interval starts after that end, emit the gap as free time; otherwise extend the coverage

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
[1,2]0
[1,3]1
[4,10]2
[5,6]3
1 · Readall intervals
2 · AskOrder by start
3 · Update state[1,2],[1,3],[4,10],[5,6]
4 · Resultprev_end = 2
Key takeaway

After merging all busy intervals, the single gap [3,4] is the common free time.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 11-14Flatten and sort

    A generator pools every employee's intervals into one stream sorted by start.

  2. 2
    Lines 16Seed coverage

    prev_end starts as the end of the earliest interval, the right edge of the first busy block.

  3. 3
    Lines 17-22Sweep for gaps

    A start beyond prev_end reveals free time; otherwise extend prev_end to the max end seen.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • Employees whose busy blocks fully tile the timeline yield an empty result
  • Nested intervals like [1,10] containing [2,3] must not create a spurious gap
  • Adjacent blocks touching at a point (end == next start) produce no free interval
  • A single employee with a single interval yields no finite free time
!

Common beginner mistakes

  • Using '>=' when comparing next start to prev_end and emitting zero-length free intervals at touching boundaries
  • Forgetting to take max(prev_end, iv.end) so a nested interval shrinks coverage
  • Accidentally reporting the unbounded free time before the first or after the last interval
Check your understanding

Why can we ignore which employee an interval belongs to when computing common free time?

More in Intervals and Sweep Line

#56Merge IntervalsSort by start, then sweep-and-merge#57Insert IntervalThree-phase interval splice#435Non-overlapping IntervalsGreedy: sort by end, keep earliest finisher#253Meeting Rooms IISweep line / min-heap of end times#228Summary RangesGroup consecutive runs#252Meeting RoomsSort by start, check adjacent overlap