p86 — Meeting Rooms II

Source: LeetCode 253 · Medium · Topics: Heap, Sweep Line, Greedy Companies (2024–2025): Amazon (very high), Google (high), Meta (high), Microsoft (medium), Bloomberg (medium) Loop position: The canonical “two ways to solve it” problem. Min-heap of end times OR sweep line on events. Knowing both — and when to use each — separates Mid from Senior.

1. Quick Context

Given meeting intervals [start, end), return the minimum number of rooms required so no two simultaneous meetings share a room.

Two solutions:

• Min-heap of end times: Sort by start. For each meeting, if the earliest-ending room is free (heap top ≤ current start), reuse it; else allocate a new room. Push current end. Answer = heap size.
• Sweep line: Sort starts and ends separately. Walk two pointers; on start ≤ end, rooms++; else rooms–. Max value = answer. (Or sort all events; +1 for start, -1 for end.)

2. LeetCode Link + Attempt Gate

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

STOP. 25-min timer. Try both approaches; compare.

3. Prerequisite Concepts

• Min-heap (heapq) for “earliest end” lookup.
• Sweep-line event aggregation.
• Half-open intervals [start, end).

4. How to Approach (FRAMEWORK 1–9)

1. Restate: Min number of rooms to host all meetings simultaneously.

2. Clarify: Open intervals? [start, end) means end == next_start shares no overlap → can reuse room.

3. Examples: [[0,30],[5,10],[15,20]] → 2.

5. Brute: For each meeting, scan all others to find overlap; build conflict graph; chromatic number. NP-hard in general but polynomial for interval graphs.

6. Target: O(n log n).

7. Pattern: Min-heap of end times OR sweep line.

8. Develop: see solution.py.

9. Test: all overlapping (n rooms); none overlapping (1); touching (end == start reuses); empty input.

5. Progressive Hints

See hints.md.

6. Deeper Insight

6.1 Min-heap solution — why it’s correct

Sort by start. When meeting i begins, the min-heap holds end times of currently-in-use rooms. If heap_min ≤ start_i, that room is free — reuse it (pop, push new end). Else allocate new room (push new end).

Exchange argument: any policy uses at least max overlap rooms. The heap-greedy never uses more, because it only opens a new room when every existing room is still busy.

6.2 Sweep-line solution — the events view

Aggregate +1 at every start, -1 at every end. Sort. Sweep and track running sum; max sum = answer.

Tie-break: when start time == end time, process end first (because [start, end) means the meeting ended before the new one starts; they share no overlap). Sort key: (time, +1 for start | -1 for end) — end comes first since -1 < +1.

6.3 Heap vs sweep: which is preferable?

• Heap if you need the actual room assignment per meeting.
• Sweep if you only need the count (slightly faster, simpler).
• Sweep wins on streaming pre-sorted events.
• Heap wins when meetings have features (priorities) and you must pick which to evict.

6.4 The (time, kind) tie-break trap

In sweep line, on tied times, end events must come before start events for half-open intervals [start, end). The natural sort (time, +1) puts ends first because -1 < +1 — but only if you encode ends as -1 and starts as +1. The opposite encoding requires explicit care.

6.5 Equivalent: max overlap = chromatic number of interval graph

This is the famous result that interval graphs are perfect — chromatic number equals max clique = max overlapping intervals at any instant. The greedy here is the constructive proof.

6.6 Family: heap-of-times / sweep-line

• LC 253 Meeting Rooms II (this).
• LC 1094 Car Pooling (sweep + cumulative passengers).
• LC 731/732 Calendar II/III (segment tree or sweep line).
• LC 1851 Minimum Interval to Include Each Query (sort + heap).
• LC 218 The Skyline Problem (sweep + heap with lazy deletion).

7. Anti-Pattern Analysis

1. Use closed intervals — [0,30] and [30,60] then “overlap”; produces 2 rooms instead of 1.
2. Sweep line tie-break wrong — sort starts and ends with (time, +1/-1) but flip the sign; produces n+1 instead of n.
3. Heap not sorted by start — pop arbitrary end times; never matches the time progression.
4. O(n²) overlap counting — works but signals you missed the pattern.
5. Build a Gantt-chart 2D bitmap — works for small inputs only; not interview-worthy.
6. Forget that touching intervals reuse the room — off-by-one on the comparison (< vs ≤).

8. Skills & Takeaways

• Min-heap of “what’s currently in use”.
• Sweep line for event aggregation.
• Tie-break rules for half-open intervals.

9. When to Move On

• Solve both ways cold in 15 min.
• Articulate which is preferable when.
• Cite LC 1094 Car Pooling as the +1/-1 sibling.

10. Company Context

• Amazon: L4/L5; one of the most common phone screens of the decade.
• Google: L5; expects both solutions.
• Meta: E4/E5; standard.
• Microsoft: L4; calendar-flavored.

Strong: “Two solutions: min-heap of end times O(n log n) and sweep-line O(n log n); chose heap when room assignment needed, sweep otherwise; cited Car Pooling and Skyline as siblings.”

11. Interviewer’s Lens

12. Level Delta

• Mid (L4): Heap solution with guidance; sweep after hint.
• Senior (L5): Both cold; correct tie-break; cites family.
• Staff (L6): + cites interval-graph perfection; + Skyline generalization.
• Principal (L7+): + recognizes this as graph coloring on interval graphs (polynomial) vs general chromatic-number (NP-hard) + cites real-world scheduling LP: integrality gap is 1 for interval graphs.

13. Follow-up Q&A

Q1: Return the actual room assignment. A1: Heap holds (end, room_id). On reuse, the popped room_id is assigned to the new meeting; else allocate next room_id.

Q2: Rooms have different capacities; meetings have attendee counts. A2: Becomes bin-packing flavored; NP-hard for arbitrary capacities. Approximations: first-fit decreasing.

Q3: Meetings have priorities; if not enough rooms, drop lowest priority. A3: Max-heap of accepted meetings by priority; on conflict, replace if new priority > min in heap. Similar to Course Schedule III.

Q4: Streaming meetings (online). A4: Maintain heap of end times; per arrival O(log n).

Q5: What’s the minimum number of rooms if meetings can be rescheduled within [start, deadline]? A5: Becomes a scheduling problem with windows; LP / max-flow.

14. Solution Walkthrough

See solution.py:

• min_meeting_rooms_heap — min-heap of end times.
• min_meeting_rooms_sweep — sweep line on events.
• min_meeting_rooms_brute — count max overlap at every start time.

15. Beyond the Problem

Principal code review: “Meeting Rooms II is the graph-coloring problem in disguise — and the only reason it’s polynomial is that the underlying conflict graph is an interval graph, which is perfect. The two solutions are dual: the heap explicitly builds the coloring (each room is a color); the sweep computes the max clique (max simultaneous overlap), and perfection of interval graphs guarantees these are equal. At Staff+, recognize this is a special case of a deep theorem: graph coloring is NP-hard in general, polynomial for perfect graphs, and interval graphs are the canonical perfect graph. The lesson scales: when you face a ‘min resources for tasks with conflicts’ problem in production (CI scheduling, GPU allocation, DB connection pooling), if you can show the conflict graph is interval (or even chordal), you get a polynomial-time optimal scheduler for free. If not, you’re in NP-hard territory and your best bet is LP relaxation or rounding heuristics.”