Hints — p50 Employee Free Time

Hint 1. Decompose: “free time across ALL employees” = “complement of (UNION of all busy times)”. Union of intervals = MERGE. Complement = INVERT.

Hint 2. Approach A (simplest): flatten everyone’s intervals into one big list, sort by start, run Merge Intervals (p46). The free time = gaps [merged[i-1].end, merged[i].start] where merged[i-1].end < merged[i].start.

Hint 3. Clip semantics: LC 759 excludes time BEFORE the first event and AFTER the last event. Only “between” gaps count.

Hint 4. Approach B (better for large K small per-employee): K-way merge with a min-heap of (start, employee_idx, interval_idx). Process intervals in start-order; track max_end_so_far. When the next start > max_end, emit a free slot.

Hint 5. In Approach B, why track max_end_so_far and not just the last popped end? Because intervals can be NESTED: a long interval popped early might extend far beyond several short later-popped intervals. The merged “busy envelope” is max_end_so_far.

If still stuck: see solution.py.