Employee Free Time: Gaps in a Merged Union of Schedules

If you interview at Google, Airbnb, Meta, expect some version of "Employee Free Time". It is rated Hard, and it falls squarely into the Merge Intervals pattern — pattern-first preparation beats grinding random problems every time. Part 8 of 11 in the Merge Intervals arc.

The Problem

Given a schedule per employee — each a sorted list of disjoint intervals — return the finite intervals of common free time, sorted. Labeled hard, but decomposes into two things this arc already covered: merge all busy intervals, then read out the gaps between merged blocks.

Input:  schedule = [[[1, 3], [6, 7]], [[2, 4]], [[2, 5], [9, 12]]]
Output: [[5, 6], [7, 9]]
Everyone is simultaneously free between 5 and 6, and between 7 and 9.

Recognizing the Merge Intervals Pattern

Interval problems — scheduling, calendars, resource booking — almost all reduce to one move: sort by start (or end), then sweep once while comparing each interval against a running boundary. Overlap exists when the next start is at most the current end. Sort plus linear sweep, O(n log n), is the backbone of the entire family.

Common free time is the complement of the union of busy time. Union of many interval lists is Merge Intervals on the flattened input; complements of a merged list are just consecutive-pair gaps. Hard problems that factor into two knowns are a recurring FAANG construction — practice spotting the factorization.

The Approach

Flatten all schedules, sort by start, merge overlaps exactly as in the canonical problem. Then walk the merged list and emit a gap whenever the next start exceeds the current end. Unbounded free time before the first and after the last interval is excluded by construction.

The k-way-heap alternative merges the pre-sorted lists in O(n log k) — mention it as the optimization when k is large and lists are long, then implement the simple version unless asked.

Python Solution

def employee_free_time(schedule: list[list[list[int]]]) -> list[list[int]]:
    """Finite intervals where every employee is free."""
    busy = sorted(
        (iv for person in schedule for iv in person),
        key=lambda iv: iv[0],
    )
    if not busy:
        return []

    free: list[list[int]] = []
    current_end = busy[0][1]
    for start, end in busy[1:]:
        if start > current_end:
            free.append([current_end, start])
            current_end = end
        else:
            current_end = max(current_end, end)
    return free

Complexity

• Time: O(n log n) — n total intervals across all employees, dominated by the sort
• Space: O(n) — flattened list plus output

Interview Tips and Follow-Ups

• Decompose out loud before coding: union then complement. Interviewers grade the decomposition on hard-labeled problems more than the code.
• The heap merge (O(n log k)) is the expected answer if the interviewer says 'millions of employees' — have the transition ready.
• Watch the envelope case in the merge (an interval entirely inside the current block) — same max-extension bug as the canonical problem.

If this clicked, continue the Merge Intervals arc in the Technical Interview category. One hundred questions, nine patterns, all in Python.