Employee Free Time

Employee Free Time asks: given everyone's busy schedules, when is everyone free at the same time? It is a classic interval-merging problem — the same sweep you use to merge meeting times, dressed up for a team.

The slow way first

You could build a minute-by-minute timeline and mark every busy slot, then scan for the unmarked stretches. That works for small numbers but blows up: the time range can be huge, so a per-unit sweep is wasteful and only handles integer times. We want something that depends on the number of intervals, not the size of the clock.

The question to ask: if I lined up every busy interval on one timeline, where would the gaps be? The gaps between the combined busy blocks are exactly the free time.

The idea: flatten, sort, merge, read the gaps

Forget which employee owns which interval — free time only cares about when someone is busy. So:

1. Flatten every employee's intervals into one big list.
2. Sort that list by start time, so overlapping blocks sit next to each other.
3. Merge overlaps into combined busy blocks.
4. Each gap between two consecutive merged blocks is a free interval.

The key insight: after sorting, you sweep left to right holding one current merged block. If the next interval starts at or before the current end, it overlaps — extend the end. If it starts later, the space in between is free, so emit it and start a new block.

Walk through it

Step through the animation. The four busy intervals are already flattened and sorted: [1,3], [2,4], [6,7], [8,10]. The pointer i sweeps right. [2,4] overlaps [1,3], so they merge into [1,4]. Then [6,7] starts after 4, so [4,6] is free and a new block begins. Finally [8,10] starts after 7, so [7,8] is free.

Pseudocode

intervals = flatten every employee schedule into one list
sort intervals by start
free = empty list
cur = first interval
for each next interval after the first:
    if next.start <= cur.end:          # overlap
        cur.end = max(cur.end, next.end)
    else:                              # a gap
        free.append([cur.end, next.start])
        cur = next
return free

The Python solution

def employee_free_time(schedule):
    intervals = [iv for emp in schedule for iv in emp]
    intervals.sort(key=lambda iv: iv[0])
    free = []
    cur = intervals[0]
    for nxt in intervals[1:]:
        if nxt[0] <= cur[1]:
            if nxt[1] > cur[1]:
                cur[1] = nxt[1]
        else:
            free.append([cur[1], nxt[0]])
            cur = nxt
    return free

• The list comprehension flattens every employee emp and every interval iv into one list.
• We sort by start (iv[0]) so overlapping busy blocks line up next to each other.
• cur is the current merged busy block. We seed it with the first interval.
• Line 7 checks overlap: if nxt starts at or before cur's end, they touch — extend cur's end if nxt reaches further.
• Otherwise (line 10) there is a gap: the stretch [cur.end, nxt.start] is free, so we record it and move cur to nxt.

Complexity

Sorting dominates, so the whole thing is O(n log n) time and O(n) space for the flattened list. (With a heap that merges already-sorted per-employee lists you can shave the constant, but the asymptotics are the same.)

When this pattern shows up

Practice