FAANG · LeetCode #253

Meeting Rooms II — three-stage drill

1The ProblemMedium

Meeting Rooms II

Fewest rooms to fit every meeting — the peak number of concurrent meetings.

Examples

[[0,30],[5,10],[15,20]]→ 2[[7,10],[2,4]]→ 1

constraintHalf-open intervals — a meeting ending at t and another starting at t share a room (end event processed before start at equal t).

2The PatternTIME O(n log n) · SPACE O(n)

Intervals

Given a pile of ranges, sort them by start — now any overlap is a neighbour, so a single left→right pass handles them.

Problems using this pattern

3The SolutionRESULT → 3

Step through it

given: 4 meetings · how many rooms do we need so every meeting has one?

Step 1 / 11

Python▎split into events · sweep · track the peak

1def minMeetingRooms(intervals):
2    starts = sorted(iv[0] for iv in intervals)
3    ends   = sorted(iv[1] for iv in intervals)
4    rooms = best = i = j = 0
5    while i < len(starts):
6        if starts[i] < ends[j]:
7            rooms += 1; i += 1          # a meeting begins
8            best = max(best, rooms)
9        else:
10            rooms -= 1; j += 1          # a meeting ends, free a room
11    return best

why it worksSplit each meeting into two events on a timeline: +1 at its start, −1 at its end. Sort the events (ends before starts on ties). Sweep left→right, keep a running count of rooms in use, and remember the running max — that max is the answer. The geometry is exact: the peak height of the bar-stack at any moment is the number of meetings happening simultaneously. O(n log n) for the sort, O(n) for the sweep.

Arrow keys to navigate · escape to reset

All problems by pattern

Two Pointers

Sliding Window

Prefix Sum

Monotonic Deque

Shortest Subarray with Sum at Least K

Binary Search

Arrays & Hashing

Monotonic Stack

Intervals

Meeting Rooms II — three-stage drill

Meeting Rooms II

Intervals

Step through it

All problems by pattern

Two Pointers

Sliding Window

Prefix Sum

Monotonic Deque

Binary Search

Arrays & Hashing

Monotonic Stack

Intervals

Heap / Top-K

Backtracking

Recursive Descent