FAANG · LeetCode #759

Employee Free Time — three-stage drill

1The ProblemHard

Employee Free Time

Time windows when EVERY employee is free at the same time.

Examples

[[[1,3],[6,8]],[[2,4],[7,11]],[[9,12]]]→ [[4,6]][[[1,2],[5,6]],[[1,3]],[[4,10]]]→ [[3,4]]

constraintEach employee's blocks are already sorted and non-overlapping; output free intervals must have positive length.

2The PatternTIME O(n log n) · SPACE O(n)

Intervals

Given a pile of ranges, sort them by start — now any overlap is a neighbour, so a single left→right pass handles them.

Problems using this pattern

3The SolutionRESULT → [[4,6]]

Step through it

given: 3 employees' schedules · find times when EVERYONE is free

Step 1 / 8

Python▎flatten · sort · sweep · gaps are free time

1import heapq
2 
3def employeeFreeTime(schedule):
4    flat = sorted([iv for emp in schedule for iv in emp],
5                  key=lambda iv: iv[0])
6    free = []
7    cur_s, cur_e = flat[0]
8    for s, e in flat[1:]:
9        if s > cur_e:                # gap — emit, then open new block
10            free.append([cur_e, s])
11            cur_s, cur_e = s, e
12        else:                        # overlap — extend running block
13            cur_e = max(cur_e, e)
14    return free

why it worksThree employees, one number line. Flatten every employee's blocks into one list, sort by start. Sweep left→right, extending one running 'busy' block whenever the next block overlaps; when the next block starts strictly AFTER the running end, the difference between them is free time — emit it and start a new running block. The 'common free' question reduces to 'gaps in the union' once you stop caring who is busy. O(N log N) where N is the total block count.

Employee Free Time — three-stage drill