p49 — Meeting Rooms II

Source: LeetCode 253 · Medium · Topics: Array, Two Pointers, Heap, Greedy, Sorting Companies (2024–2025 frequency): Meta (very high), Google (very high), Amazon (high), Microsoft (high), Apple (medium-high), Uber (high), LinkedIn (medium-high), Airbnb (medium) Loop position: TOP-5 most-asked Medium overall. Multiple optimal solutions; tests breadth (heap vs sweep vs two-pointer) plus depth (capacity, k=peak, online variants).

1. Quick Context

Given a list of meeting intervals, return the minimum number of rooms needed.

Equivalent: at the busiest point, how many meetings overlap?

Two classical optimal solutions, both O(n log n):

Solution A — Min-heap of end-times

1. Sort meetings by start.
2. Walk through; before scheduling each meeting, pop the heap WHILE its top end-time ≤ current start (those rooms are free).
3. Push current end. Heap size = rooms currently in use.
4. Answer = max heap size ever reached.

intervals.sort(key=lambda x: x[0])
heap = []   # end times
for s, e in intervals:
    if heap and heap[0] <= s:
        heapq.heappop(heap)
    heapq.heappush(heap, e)
return len(heap)

Wait — that returns the FINAL heap size, not the peak. Need to track max. Or: pop ALL releasable rooms, then push (a) returns the right count when done correctly. See solution.py for the safe form.

Solution B — Two-pointer / sweep over starts and ends

1. Sort starts and ends INDEPENDENTLY.
2. Walk a pointer s through starts and a pointer e through ends.
3. If starts[s] < ends[e]: a new meeting begins before an old one ends → active++, s++.
4. Else: a meeting ends → e++, active--.
5. Track max active.

starts = sorted(i[0] for i in intervals)
ends   = sorted(i[1] for i in intervals)
s = e = active = peak = 0
while s < len(starts):
    if starts[s] < ends[e]:
        active += 1; peak = max(peak, active); s += 1
    else:
        active -= 1; e += 1
return peak

O(n log n) sort + O(n) sweep. Often the FASTEST in practice (constant factors).

Both solutions are excellent; producing both demonstrates breadth.

2. LeetCode Link + Attempt Gate

🔗 https://leetcode.com/problems/meeting-rooms-ii/

STOP. 15-min timer. Can you produce BOTH solutions?

3. Prerequisite Concepts

• heapq (Python min-heap).
• Two-pointer sweep.
• Sweep-line / event processing.
• Half-open semantics: a meeting ending at 10 frees the room for a meeting starting at 10.

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

Step 1 — Restate: “Find the maximum point-multiplicity over the union of intervals.” (Or: min chromatic number of the interval graph — for interval graphs, equal to clique number = max overlap.)

Step 2 — Clarify:

• “Half-open or closed? Does a meeting [0, 10] and another [10, 20] need 1 room or 2?” (LC 253: half-open — 1 room.)
• “All non-negative times?” (Yes.)
• “Empty input → 0 rooms?” (Yes.)
• “Are times integers or floats?” (Doesn’t change algorithm.)

Step 3 — Constraints: n ≤ 10^4. O(n log n) trivially fits.

Step 4 — Examples:

• [[0,30],[5,10],[15,20]] → 2.
• [[7,10],[2,4]] → 1 (disjoint).
• [[0,10],[10,20]] → 1 (half-open touch).
• [] → 0.
• [[1,5],[2,6],[3,7],[4,8]] → 4 (full overlap stack).

Step 5 — Brute force: For each minute from min_start to max_end, count active. O((max_end - min_start) × n). Quadratic-ish in time-range.

Step 6 — Complexity: Both heap and two-pointer are O(n log n). Sweep-line with (time, ±1) events also O(n log n).

Step 7 — Pattern: Sweep-line / interval-graph chromatic number / scheduling-with-resources.

Step 8 — Develop: see solution.py.

Step 9 — Test: empty; single meeting; all disjoint; all back-to-back (no overlap); full pyramid stack; many duplicates at one moment.

5. Progressive Hints

If stuck for 5 min, open hints.md.

6. Deeper Insight — Three lenses on the same problem

6.1 Lens 1 — Interval graph chromatic number

Build a graph: each meeting = vertex; edge between two if they overlap. The min rooms = chromatic number (color each meeting; same-color meetings go in the same room since they don’t overlap).

For general graphs, chromatic number is NP-hard. For interval graphs, it equals the clique number (max set of pairwise-overlapping intervals) = max point multiplicity. This is solvable in O(n log n) via the sweep, which is what we’re doing.

This connects to graph coloring / scheduling theory; mention as senior+ insight.

6.2 Lens 2 — Sweep-line with events

Create events: (start, +1) and (end, -1). Sort by time, with -1 before +1 at the same time (half-open: end at t frees room before a new meeting starts at t).

Walk events; maintain running count; track max.

events = [(s, 1) for s, _ in intervals] + [(e, -1) for _, e in intervals]
events.sort(key=lambda x: (x[0], x[1]))   # -1 sorts before +1 at same time
peak = active = 0
for _, delta in events:
    active += delta
    peak = max(peak, active)

This is the most general approach; generalizes to “max k overlapping” by checking active vs k.

6.3 Lens 3 — Heap as live “rooms in use”

Each heap entry = end time of a room currently in use. When a new meeting starts, check if the earliest-ending room has been freed by then (its end ≤ new start). If yes, reuse (pop). Push the new meeting’s end.

Subtle: pop one or pop all?

• Pop one at a time: works if you also track max(len(heap)) after each push.
• Pop all that are releasable, then push: heap size after push = exactly current rooms in use; final max is the answer.

The careful form is in solution.py. The classic LC editorial pops at most ONE per iteration, which works because if heap[0] > start, no further pops would help anyway (no room is free).

6.4 Why heap vs two-pointer are equivalent

The two-pointer sweep is the heap algorithm in disguise:

• The ends array is essentially the sorted heap (since all ends are known up front).
• starts[s] < ends[e] ↔ “no room free; need new room” (active++).
• Else ↔ “earliest-ending room frees” (active–).

The two-pointer is faster by a constant factor because it avoids heap overhead, but the heap version is more general (e.g., if room capacities differ).

6.5 Generalization: K-overlap question

“How many points are covered by ≥ k intervals?” — sweep-line and accumulate ranges where active ≥ k. O(n log n).

“What’s the smallest set of intervals to remove so that no point has > k coverage?” — harder; greedy by end works with priority queue.

6.6 Online variant: streaming meetings

If meetings arrive in real time and you must commit a room immediately:

• Maintain a heap of (room_id, end_time).
• For new meeting: pop one room whose end ≤ new start (free); if available, reuse; else allocate a new room.
• Total rooms = max over time.

This is the actual production algorithm (room booking systems). The LC problem is the batch version.

6.7 Capacity per room / weighted rooms

If rooms have different sizes (e.g., 5-person vs 10-person), the problem becomes bin packing for some variants — NP-hard. For “any room can fit any meeting” it remains O(n log n).

7. Anti-Pattern Analysis

1. Use <= instead of < for “new start before old end” in the two-pointer: misses the half-open semantics, overcounts by 1 in touching cases.
2. Sort starts and ends together as pairs — destroys the two-pointer trick. Sort them independently.
3. For the heap version, forget that pushing also counts — need to track max BEFORE the push or AFTER properly.
4. Build a minute-by-minute boolean array — works only when times are small integers; awful otherwise.
5. Sort by end first — wrong for the heap solution; need to process arrivals in chronological order.
6. Pop ALL releasable rooms first, then check if heap is empty before pushing — correct, but if you check len(heap) AFTER push, the answer is correct AS the running max.
7. Treat overlap as closed <= when problem is half-open — common bug.
8. Forget empty-input edge case — heap[0] raises IndexError; guard with if heap and heap[0] ≤ s.
9. Conflate “min rooms” with “max overlap” in writing but compute one and return the other — they’re equal, but verbalize precisely.

8. Skills & Takeaways

• Three lenses on the same problem: chromatic number, sweep-line, heap.
• Two-pointer trick of sorting starts and ends independently.
• heapq for “rooms in use” model.
• Sweep-line with (time, ±1) events as a universal sledgehammer for active-count problems.
• Half-open vs closed changes one operator.

9. When to Move On

Move on when:

• You can write BOTH the heap and two-pointer versions in ≤ 15 min total.
• You can articulate the chromatic-number / interval-graph connection.
• You can sketch the online variant.
• Stress test on 1000 random inputs agrees with brute minute-sweep.

10. Company Context

Meta:

• Top-5 phone-screen Medium. L4/L5 must produce one optimal solution + edge-case test.
• L6: must produce BOTH solutions and discuss trade-offs.
• Bar Raiser: “Two solutions; articulated half-open semantics; mentioned sweep-line generalization.”

Google:

• L4-L6. Almost always followed by “now what if rooms have capacities?” or “what’s the longest free slot?”

Amazon:

• L5+. Productized as “warehouse loading dock allocation.”

Microsoft:

• L62+. Often paired with LC 252 Meeting Rooms I (just feasibility check).

Apple:

• Calendar team. Variant: “show me all conflicts” → sweep-line output.

Uber:

• “Maximum concurrent rides” — same problem with productized framing.

LinkedIn:

• Scheduling conflict detection.

11. Interviewer’s Lens

12. Level Delta

Mid (L4):

• One clean solution (heap or two-pointer).
• Handles half-open correctly.
• Empty input.

Senior (L5):

• Both solutions in interview time.
• Recognizes equivalence between approaches.
• Mentions sweep-line generalization.

Staff (L6):

• Interval-graph chromatic-number framing.
• K-overlap generalization.
• Capacity-per-room → bin-packing observation.
• Online variant sketch.

Principal (L7+):

• Discusses distributed room allocation for global meeting systems (CRDTs, conflict resolution).
• Discusses integer programming for variants with hard constraints (e.g., specific room features required).
• Discusses competitive online algorithms with adversarial schedules.
• Discusses cache-friendly sweep implementations at scale.

13. Follow-up Q&A

Q1: What if I want to know the actual ASSIGNMENT (which meeting → which room)? A: Modify the heap to store (end_time, room_id). When you pop, that room is the one assigned to the new meeting. Maintains room_id consistency.

Q2: What’s the longest stretch of time with ZERO meetings? A: Sweep-line; track times when active drops to 0 and how long it stays there.

Q3: K-overlap — at how many points is overlap ≥ k? A: Sweep; when active crosses k upward, mark start; when it falls below k, close range; sum range lengths.

Q4: Closed intervals — does it change? A: Yes — at the same time t, processing -1 after +1 would erroneously double-count. Sort with +1 before -1 for closed semantics.

Q5: Online — meetings arrive in real time? A: Heap of (end, room_id). On arrival: pop one if heap[0].end ≤ start; reuse or allocate new. Total rooms = max ever allocated.

Q6: Capacity-aware (rooms have sizes; meetings have attendee counts)? A: Becomes a matching problem. Approximation: sort meetings by size desc; for each, pick smallest available room that fits. Online competitive algorithms exist; offline can be solved with min-cost flow.

14. Solution Walkthrough

See solution.py:

• min_meeting_rooms_heap — sort + min-heap. O(n log n).
• min_meeting_rooms_two_pointer — sort starts and ends independently. O(n log n).
• min_meeting_rooms_sweep_line — (time, ±1) events. O(n log n).
• min_meeting_rooms_brute — minute-by-minute counting (oracle).
• edge_cases() + stress_test().

Run: python3 solution.py.

15. Beyond the Problem

Principal-engineer code review comment:

“This is the problem we use to filter for ‘has actually shipped a calendar system.’ Three things separate the great answers from the merely correct: (1) The candidate ASKS about endpoint semantics BEFORE writing the algorithm — because in production, that decision (half-open vs closed) is made at the API contract layer, and the algorithm follows. (2) The candidate produces TWO optimal solutions and articulates the equivalence — that means they understand the problem, not just memorized one approach. (3) When I ask ‘now make it streaming,’ they don’t restart from scratch; they describe how the heap version naturally extends to online. If a candidate’s heap version is buggy on touching intervals, that tells me they’ve never actually integrated with iCal or Google Calendar APIs, because that’s the FIRST thing that breaks in production.”

Connections forward:

• p46 / p47 / p48 — Other interval problems.
• p50 — Employee Free Time (related: invert “active” to find free intervals).
• LC 252 — Meeting Rooms I (feasibility only).
• LC 1094 — Car Pooling (sweep-line with capacity).
• LC 732 — My Calendar III (online MAX active).
• LC 218 — The Skyline Problem (sweep-line + heap, harder).
• Production: meeting room allocation, car-pooling, network connection limiting, rate-limiting per resource.