095. Employee Free Time

Why this mechanism works

Everyone is free exactly outside the union of all busy intervals. Merge that union and emit its interior gaps. The finite-gap convention is essential: without a specified observation horizon, the free time outside the first and last busy intervals would be unbounded.

State and boundaries

end is the farthest endpoint of the current busy union. gaps contains finalized positive-length gaps between busy segments.

Protocol

1. Flatten and sort all busy intervals.
2. Seed the active end.
3. When a later start exceeds end, emit the gap.
4. Extend end to the larger endpoint.
5. Return only interior gaps.

Visualization

employee A: [1,3), [6,7)
employee B: [2,4)
busy union: [1,4), [6,7)
common finite gap: [4,6)

Python implementation

def employee_free_time(schedules):
    busy = sorted(interval for schedule in schedules for interval in schedule
                  if interval[0] < interval[1])
    if not busy:
        return []
    end = busy[0][1]
    gaps = []
    for start, next_end in busy[1:]:
        if start > end:
            gaps.append([end, start])
        end = max(end, next_end)
    return gaps

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L2 <genexpr>: busy = sorted(interval for schedule in schedules for interval in schedule
.0=list_iterator; schedule=[(1, 3), (6, 7)]; interval=(1, 3)

L2 <genexpr>: busy = sorted(interval for schedule in schedules for interval in schedule
.0=list_iterator; schedule=[(1, 3), (6, 7)]; interval=(6, 7)

L2 <genexpr>: busy = sorted(interval for schedule in schedules for interval in schedule
.0=list_iterator; schedule=[(1, 3), (6, 7)]; interval=(6, 7)

L2 <genexpr>: busy = sorted(interval for schedule in schedules for interval in schedule
.0=list_iterator; schedule=[(2, 4)]; interval=(2, 4)

L2 <genexpr>: busy = sorted(interval for schedule in schedules for interval in schedule
.0=list_iterator; schedule=[(2, 4)]; interval=(2, 4)

L2 employee_free_time: busy = sorted(interval for schedule in schedules for interval in schedule
schedules=[[(..., ...), (..., ...)], [(..., ...)]]; busy=[(1, 3), (2, 4), (6, 7)]

L6 employee_free_time: end = busy[0][1]
schedules=[[(..., ...), (..., ...)], [(..., ...)]]; busy=[(1, 3), (2, 4), (6, 7)]; end=3

L7 employee_free_time: gaps = []
schedules=[[(..., ...), (..., ...)], [(..., ...)]]; busy=[(1, 3), (2, 4), (6, 7)]; end=3; gaps=[]

... 1 intermediate state changes omitted ...

L11 employee_free_time: end = max(end, next_end)
schedules=[[(..., ...), (..., ...)], [(..., ...)]]; busy=[(1, 3), (2, 4), (6, 7)]; end=4; gaps=[]; start=2; next_end=4

L8 employee_free_time: for start, next_end in busy[1:]:
schedules=[[(..., ...), (..., ...)], [(..., ...)]]; busy=[(1, 3), (2, 4), (6, 7)]; end=4; gaps=[]; start=6; next_end=7

L10 employee_free_time: gaps.append([end, start])
schedules=[[(..., ...), (..., ...)], [(..., ...)]]; busy=[(1, 3), (2, 4), (6, 7)]; end=4; gaps=[[4, 6]]; start=6; next_end=7

L11 employee_free_time: end = max(end, next_end)
schedules=[[(..., ...), (..., ...)], [(..., ...)]]; busy=[(1, 3), (2, 4), (6, 7)]; end=7; gaps=[[4, 6]]; start=6; next_end=7

L2 <genexpr>: busy = sorted(interval for schedule in schedules for interval in schedule
.0=list_iterator; schedule=[]

L2 employee_free_time: busy = sorted(interval for schedule in schedules for interval in schedule
schedules=[[], []]; busy=[]

Why the solution is correct

An emitted gap lies after every previous busy interval and before the next start, so no employee is working there. A merged busy span excludes every time when at least one employee works. These complementary interior regions are exactly common finite free time.

Time and space

O(N log N) time and O(N) space for N busy intervals. A k-way merge can exploit the pre-sorted employee lists more directly.

Common mistakes

Intersecting busy schedules finds common work time, not common free time. Inventing finite outer bounds changes the requested observation horizon.

Reasoning card

Transfer exercise

Add an explicit workday [open,close) so leading and trailing free time can be returned meaningfully.