Search lands in PR-5.1 (Pagefind).
How-to Intermediate

Chapter 2 Updated

Employee Free Time

Flatten, merge, then gaps between merged = free time.

  • Full 6m
  • Revision 2m
  • Flow 1m

Problem

LeetCode #759 — one-liner.

  • Given per-employee work schedules, return the intervals during which nobody is working.

Key insight

Merge everything, then read the gaps.

  • Flatten all employees’ intervals → sort by start → merge (standard Merge Intervals).
  • The gaps between merged intervals are the common free time.
  • Follow-up: if each employee’s list is already sorted, merge-K-sorted-lists via min-heap runs in O(N log K) instead of O(N log N).

Solution template

Merge, then walk the merged list.

all = [iv for e in schedule for iv in e]
all.sort(key=lambda x: x[0])
merged = [all[0]]
for iv in all[1:]:
    if iv[0] <= merged[-1][1]:
        merged[-1][1] = max(merged[-1][1], iv[1])
    else: merged.append(iv)
return [[merged[i-1][1], merged[i][0]] for i in range(1, len(merged))]

Complexity

N = total intervals.

  • Time O(N log N) — sort dominates; merge and gap-walk are linear.
  • Space O(N) — flattened + merged lists.

Edge cases

Three to remember.

  • Single employee — the “common” semantics can be ambiguous; clarify with interviewer.
  • Everyone busy end-to-end → one merged block → zero gaps → return [].
  • Pre-sorted per employee → min-heap variant is O(N log K).

Comments

Comments are disabled in this environment. Set PUBLIC_GISCUS_REPO, PUBLIC_GISCUS_REPO_ID, and PUBLIC_GISCUS_CATEGORY_ID to enable.