Hints — p86 Meeting Rooms II
-
Half-open intervals
[start, end): meeting ending at 5 and meeting starting at 5 share no overlap and can reuse the same room. -
Heap approach: sort by start time. Min-heap holds end times of in-use rooms. For each meeting, if
heap_min <= start, reuse (replace top); else push (new room). -
Sweep approach: create +1 events at starts, -1 at ends. Sort. Cumulative max = answer. At ties, end (-1) comes before start (+1) — natural sort works since -1 < +1.
-
Brute (oracle): at every meeting’s start, count how many other meetings are active. Max over starts.
-
Answer = max overlap at any instant = chromatic number of the interval conflict graph (a perfect graph, so polynomial).
If stuck: see solution.py.