p50 — Employee Free Time

Source: LeetCode 759 · Hard · Topics: Heap, Sorting, Sweep Line, Greedy Companies (2024–2025 frequency): Google (high), Meta (medium-high), Amazon (medium), Microsoft (medium), Bloomberg (medium), LinkedIn (medium-high) Loop position: Senior+ Hard. Brings together the entire Intervals toolkit — merge, multi-list merge, invert. The “synthesis” question.

1. Quick Context

You’re given schedule, a list of K employees’ busy times. Each employee’s busy times are sorted and disjoint. Return the time slots that are FREE for ALL employees, sorted.

Two approaches:

Approach A — Flatten, sort, merge, invert

1. Flatten all employees’ intervals into one big list.
2. Sort by start.
3. Merge overlapping (p46).
4. The free time = gaps BETWEEN consecutive merged intervals.

O(N log N) where N = total intervals.

Approach B — K-way merge with heap, then invert on-the-fly

1. Min-heap of (start, employee_idx, interval_idx), one per employee initially.
2. Repeatedly pop earliest start; track running max-end-so-far.
3. When popped start > running max-end → emit free slot [max_end, start).
4. Update max-end = max(max-end, popped end); advance that employee’s pointer.

O(N log K). Better when K << N.

Return the gaps. Note LC returns intervals as Interval objects (with start/end attrs), not lists.

2. LeetCode Link + Attempt Gate

🔗 https://leetcode.com/problems/employee-free-time/

STOP. 15-min timer. Think: what’s the SIMPLEST decomposition? (Merge → invert.)

3. Prerequisite Concepts

• p46 Merge Intervals.
• p44 Merge K Sorted Lists (from Week 9) — K-way merge with heap.
• “Invert” pattern: given sorted disjoint busy intervals, output the gaps.

4. How to Approach (FRAMEWORK Steps 1–9)

Step 1 — Restate: “Given K sorted-disjoint interval lists, find the COMPLEMENT of their union, restricted to the time range between first and last events.”

Step 2 — Clarify:

• “Does FREE time include before the first event or after the last?” (LC: NO — only between events.)
• “Half-open or closed?” (LC: usually treated as closed-interval-style busy; a free slot is [end_i, start_{i+1}] with end_i < start_{i+1}.)
• “Can an employee have ZERO intervals?” (Edge case to ASK.)
• “Output type?” (LC: list of Interval objects.)

Step 3 — Constraints: K up to ~50, N (total intervals) up to ~10^4. Both O(N log N) and O(N log K) easily fit.

Step 4 — Examples:

• [[[1,2],[5,6]],[[1,3]],[[4,10]]] → [[3,4]] (only gap is 3-4; before 1 and after 10 don’t count).
• [[[1,3],[6,7]],[[2,4]],[[2,5],[9,12]]] → [[5,6],[7,9]].

Step 5 — Brute force: Discretize the time-axis (won’t scale beyond small ranges). Or: flatten + sort + merge + invert (which is Approach A — actually the canonical answer).

Step 6 — Complexity:

• Approach A: O(N log N).
• Approach B: O(N log K).
• For K small relative to N, B is marginally better.

Step 7 — Pattern: Multi-list merge + invert. Same family as p46/p47/p49 and p44 (Merge K Sorted).

Step 8 — Develop: see solution.py.

Step 9 — Test: single employee with gaps; everyone busy continuously (no free); employees with no intervals (skip); overlapping starts; one employee fully contains others.

5. Progressive Hints

If stuck for 5 min, open hints.md.

6. Deeper Insight

6.1 Why this is Hard despite being simple

The conceptual decomposition (merge + invert) is straightforward. What makes it Hard:

1. Multi-list input (not single list). Tests whether you flatten or do a K-way merge.
2. Inverting the answer is its own pattern that beginners miss.
3. Edge-case discipline is high: empty lists, single employee, zero gaps.
4. The Interval type instead of List[int] trips up Python solvers who assume LC-50 syntax.

6.2 The “invert” pattern, generalized

Given sorted disjoint busy intervals B = [(b1.s, b1.e), (b2.s, b2.e), ...], the free time within [B[0].s, B[-1].e] is:

• [B[0].e, B[1].s] (if B[0].e < B[1].s)
• [B[1].e, B[2].s] (if B[1].e < B[2].s)
• …

If you want free time on (-∞, ∞), also include (-∞, B[0].s] and [B[-1].e, ∞). Most problems clip to [B[0].s, B[-1].e].

This invert is reused EVERYWHERE: “find gaps between calendar events,” “find packet-loss windows in a connection log,” “find idle time on a CPU.”

6.3 K-way merge as the production approach

Approach A flattens ALL intervals upfront. For K = 10^6 employees with 10 intervals each, that’s 10^7 intervals to sort — expensive.

Approach B (heap of K items) merges lazily. Each pop is O(log K); total O(N log K). For K << N, big win.

This is the same pattern as Week 9 p44 Merge K Sorted Lists, generalized to intervals.

6.4 Why Approach B requires tracking max_end_so_far

In a K-way merge, intervals are popped in start-order BUT their ends can be in any order. To detect a gap, we need to know “what’s the furthest right any popped interval has extended?”

if cur.start > max_end:
    emit free slot [max_end, cur.start]
max_end = max(max_end, cur.end)

This is the SAME max(prev_end, cur_end) invariant from p46 Merge Intervals — applied during a streaming merge.

6.5 Sweep-line variant

Same as p49 with (time, ±1) events. Free time = stretches where active == 0. Sort all events; walk; record ranges. O(N log N). Equivalent to Approach A.

6.6 Real-world: scheduling assistants

This is literally how “Find a Time” features work in Google Calendar, Outlook, and Calendly:

1. Pull each invitee’s busy times in the query window.
2. K-way merge across invitees.
3. Invert to find free slots.
4. Filter by duration constraint (only slots ≥ 30 min, e.g.).

Production also handles timezones, working hours, recurring events — all reduced to the same primitive.

6.7 Duration-filtered variant

“Find free slots ≥ k minutes.” After computing free slots, filter [s, e] where e - s >= k. Trivial post-processing.

“Find the FIRST free slot ≥ k minutes.” Streaming variant: do the K-way merge but emit early.

7. Anti-Pattern Analysis

1. Discretize the time axis (one slot per minute) — works on toy inputs, blows up for real timestamps.
2. Forget to clip free time to [B[0].s, B[-1].e] — LC won’t accept infinite-prefix/suffix free time.
3. Naïvely treat each employee’s list separately and intersect — wrong; union (merge) is what you want, then invert.
4. For K-way merge: forget max_end_so_far — emit gaps incorrectly when an earlier-started but later-ending interval covers a “gap.”
5. Sort by end — wrong for the merge phase; sort by start.
6. Use a list of [start, end] lists when LC expects Interval objects — runtime error.
7. Heap with just start as the key — need at least (start, employee_idx, interval_idx) to disambiguate and advance.
8. Push all intervals upfront in K-way version — defeats the purpose; push one per employee, advance lazily.
9. Forget that some employees may have zero intervals in some inputs — skip them when initializing the heap.

8. Skills & Takeaways

• Decompose into “merge then invert” — the universal pattern.
• K-way merge with heap for multi-list input (reuse from Week 9 p44).
• max_end_so_far invariant during streaming merge.
• Invert pattern as a reusable primitive across calendar/scheduling problems.
• Clip to event range — semantics of “free time” excludes prefix/suffix.

9. When to Move On

Move on when:

• Approach A in ≤ 12 min from memory.
• Approach B in ≤ 20 min.
• You can explain WHY Approach B’s max_end_so_far is needed.
• You recognize this is the engine behind “Find a Time” features.
• Stress test on 200 random multi-list inputs agrees with brute discretization.

10. Company Context

Google:

• L5/L6 onsite Hard. Calendar team interviews use this as a “do you understand the production primitive?” test.
• Bar Raiser: “Decomposed into merge + invert; mentioned K-way merge for scale; ASKed about clipping semantics.”

Meta:

• L5+. Often phrased as “find common available slots for N people.”

Amazon:

• L5/L6. Productized as “find idle warehouse-dock windows.”

Microsoft:

• L62-L66. Outlook scheduling team.

Bloomberg:

• “Find market-closed windows across exchanges in different time zones.”

LinkedIn:

• Meeting-assist features; recruiting calendar tools.

11. Interviewer’s Lens

12. Level Delta

Mid (L4):

• Approach A (flatten + sort + merge + invert) working.
• Handles empty employees and single employee.
• Knows the answer excludes prefix/suffix free time.

Senior (L5):

• Approach B (K-way merge with heap), with max_end_so_far invariant.
• Explains K vs N trade-off.
• Mentions sweep-line as a third equivalent approach.

Staff (L6):

• Discusses real “Find a Time” production design (timezones, working hours, recurrence).
• Discusses duration-filtered variants.
• Discusses incremental/online versions for streaming calendar updates.

Principal (L7+):

• Discusses federated calendars (different systems, eventual consistency).
• Discusses distributed scheduling with conflict-free replicated data types.
• Discusses fairness constraints (rotating who gets prime slots in recurring meetings).
• Discusses AI scheduling assistants as a layer above this primitive.

13. Follow-up Q&A

Q1: Find free slots ≥ k minutes long? A: After computing free intervals, filter [s, e] where e - s >= k.

Q2: Find the FIRST free slot ≥ k minutes? A: Streaming variant of Approach B; emit early and return.

Q3: Find free slots across DIFFERENT TIMEZONES? A: Normalize all intervals to UTC at the API boundary, then run the algorithm. Output back in user’s local timezone.

Q4: Online — new employee added, recompute free time? A: Two options:

• Recompute from scratch: O(N log K) — fine for small K.
• Incremental: maintain merged busy list; for new employee’s intervals, run p47 Insert Interval for each; recompute invert. O((m + n) log) where m = new intervals.

Q5: K = 10^6 employees, 10 intervals each — Approach A or B? A: B. Flatten + sort would be 10^7 log 10^7 ≈ 10^8 ops; B is 10^7 log 10^6 ≈ 2 × 10^8 ops — actually similar. Real difference: B is incremental, doesn’t need to allocate the flat array.

Q6: Find times when AT LEAST k employees are busy? A: Sweep-line with (time, ±1) events; collect ranges where active >= k. O(N log N).

14. Solution Walkthrough

See solution.py:

• Interval class — minimal stand-in for LC’s type.
• employee_free_time_flatten — Approach A. O(N log N).
• employee_free_time_heap — Approach B. O(N log K).
• employee_free_time_brute — discretize timeline (oracle).
• edge_cases() + stress_test().

Run: python3 solution.py.

15. Beyond the Problem

Principal-engineer code review comment:

“This is the kind of problem where the algorithm is easy and the SYSTEMS DESIGN is hard. Three lessons from running calendar infrastructure at scale: (1) Timezones. Always normalize to UTC integers at ingest; never trust client-reported times. We had a quarter-long incident where DST transitions silently shifted entire teams’ free time by an hour. (2) Recurrence. A ‘repeating meeting’ is conceptually one event but operationally hundreds; you don’t expand it eagerly. The merge-invert primitive runs over a WINDOW; expand recurrence into that window lazily. (3) The max_end_so_far invariant in Approach B is the kind of thing that’s obvious in interview and gets dropped in production refactors. Lock it into a method with a name (extend_busy_envelope) and a comment explaining the invariant. Future-you will thank you when someone tries to ‘optimize’ it away.”

Connections forward:

• p46 — Merge Intervals (subroutine in Approach A).
• p47 — Insert Interval (subroutine for online add-employee variant).
• p49 — Meeting Rooms II (sweep-line cousin).
• p44 — Merge K Sorted Lists (heap K-way merge template).
• LC 1229 — Meeting Scheduler (2-person version).
• LC 986 — Interval List Intersections (related but intersection, not union).
• Production: Google Calendar “Find a Time”, Outlook Scheduling Assistant, Calendly, FreeBusy queries, on-call rotation finders.