Problem 40 · Intervals

Employee Free Time

HardClassic DSA & systems

01Problem

Given each employee's sorted list of non-overlapping working intervals, return the finite intervals during which all employees are free.

02Key insight

This is a k-way merge of sorted lists: pop intervals in start order from a heap, track the furthest end seen, and any gap between that end and the next start is common free time.

03Solution

solution.pypython16 lines

import heapq

def employee_free_time(schedules: list[list[list[int]]]) -> list[list[int]]:
    heap = [(sched[0][0], emp, 0) for emp, sched in enumerate(schedules) if sched]
    heapq.heapify(heap)
    free: list[list[int]] = []
    latest_end: int | None = None
    while heap:
        start, emp, idx = heapq.heappop(heap)
        end = schedules[emp][idx][1]
        if latest_end is not None and start > latest_end:
            free.append([latest_end, start])
        latest_end = end if latest_end is None else max(latest_end, end)
        if idx + 1 < len(schedules[emp]):
            heapq.heappush(heap, (schedules[emp][idx + 1][0], emp, idx + 1))
    return free

Try it first.

TimeO(N log k)

SpaceO(k)

tests.py · 4 passing

tests.pypython4 lines

assert employee_free_time([[[1, 2], [5, 6]], [[1, 3]], [[4, 10]]]) == [[3, 4]]
assert employee_free_time([[[1, 3], [6, 7]], [[2, 4]], [[2, 5], [9, 12]]]) == [[5, 6], [7, 9]]
assert employee_free_time([[[1, 2]], [[2, 3]]]) == []
assert employee_free_time([[], []]) == []

04Staff-level follow-up

Calendar service for 100k employees and 'find a slot for these 8 people'? Only merge the 8 attendees' busy lists fetched from a per-user free/busy index, bounded to the query window; time zones and working hours become additional busy intervals.