How-to Intermediate

Chapter 2 Updated April 21, 2026

Meeting Rooms II — Minimum Rooms

Min-heap of end times, or sweep-line with +1 / -1 events.

Full 8m
Revision 3m
Flow 2m

LeetCode #253 — one-liner.

Given meeting intervals, return the minimum number of conference rooms that can hold them all.

Peak concurrency = answer.

Answer = maximum number of meetings active at any one time.
Two canonical ways to compute it: min-heap of end times (sorted by start) and sweep line of +1/-1 events.
FAANG follow-up: know at least two of the three approaches cold.

Heap and sweep in five lines each.

# A: min-heap
intervals.sort(key=lambda x: x[0])
heap = [intervals[0][1]]
for s, e in intervals[1:]:
    if s >= heap[0]: heapq.heappop(heap)
    heapq.heappush(heap, e)
return len(heap)
 
# B: sweep line
events = [(s, 1) for s, _ in intervals] + [(e, -1) for _, e in intervals]
events.sort(key=lambda x: (x[0], x[1]))
peak = cur = 0
for _, d in events:
    cur += d
    peak = max(peak, cur)

Same big-O, different constants.

Time O(n log n) — sort dominates in both approaches.
Space O(n) — heap (≤ n ends) or events (2n).

Four to remember.

No meetings → return 0.
No overlaps → heap/peak stays at 1.
All meetings at the same time → answer = n.
Back-to-back [1,2] + [2,3] → end (-1) sorts before start (+1) at time 2, so peak stays at 1 (one room suffices).

Comments

Comments are disabled in this environment. Set PUBLIC_GISCUS_REPO, PUBLIC_GISCUS_REPO_ID, and PUBLIC_GISCUS_CATEGORY_ID to enable.