253. Meeting Rooms II

253

MediumIntervals and Sweep LineMin-heap (priority queue)Sweep line / min-heap of end times

Meeting Rooms II

Given an array of meeting time intervals where intervals[i] = [start_i, end_i], return the minimum number of conference rooms required so that no two overlapping meetings share a room.

Open official problem prompt ↗

In plain English

Compute the peak number of meetings happening at the same instant, which equals the minimum rooms needed.

Picture it like this

Like watching a parking lot: every arriving car needs a spot, and a spot frees only when a car leaves; the most cars parked at once is how many spots you must have.

Example

Input: intervals = [[0,30],[5,10],[15,20]]
Output: 2
Why: [0,30] runs the whole time; [5,10] needs a second room, and [15,20] can reuse that second room after [5,10] ends.

Constraints

1 <= intervals.length <= 10^40 <= start_i < end_i <= 10^6

Pattern lesson

See the pattern, then code

Sweep line / min-heap of end times

↗

Intervals and Sweep Line

Meetings, schedules, overlapping ranges, resource allocation, or timeline events.. Sort meetings by start; a min-heap holds the end times of meetings currently occupying rooms, and the heap size at its peak is the number of rooms you need.

New words, made simpleKnow these before the algorithm

Min-heap: A priority queue whose smallest element (here the earliest end time) is always at the top.
Concurrency: How many intervals are simultaneously active at a point in time.
Sweep line: Processing sorted event points left to right, adjusting a running count.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Brute-force overlap count

Too slow and doesn't directly give peak concurrency.

For each interval count how many others overlap it and take the max.

Time O(n^2)Space O(1)

Two sorted arrays / chronological sweep

Optimal and heap-free, an equally valid alternative.

Sort starts and ends separately; sweep two pointers incrementing on a start and decrementing on an end.

Time O(n log n)Space O(n)

Best choiceMin-heap of end times

Directly models rooms and keeps the running maximum as heap size.

Process meetings by start; reuse a room when the earliest end has passed, otherwise open a new one.

Time O(n log n)Space O(n)

The rule we keep true

Invariant

The heap always contains exactly the end times of meetings that are still occupying a room at the current meeting's start, so its size equals the rooms in use right now.

Why this is correct

Reasoning

Sorting by start means when we reach a meeting, every earlier-started meeting has been placed. Freeing rooms whose end <= current start reflects real availability; because we never free more than possible, the largest the heap ever grows is exactly the maximum simultaneous overlap, the true room requirement.

The algorithm in three movesSay these aloud before coding

1Sort meetings by start time

push 30 -> heap=[30] rooms=1

2Keep a min-heap of end times of ongoing meetings

5<30 no free, push -> heap=[10,30] rooms=2

3For each meeting, pop any meeting that has already ended (end <= current start) to free its room

15>=10 pop, push 20 -> heap=[20,30] rooms=2

4Push the current meeting's end; the maximum heap size is the answer

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

[0,30]0

[5,10]1

[15,20]2

1 · Read[[0,30],[5,10],[15,20]]

2 · AskOrder by start?

3 · Update stateheap = []

4 · Resultalready sorted

Key takeaway

At time 5 both [0,30] and [5,10] are active, forcing two rooms.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 5Sort by start
Processes meetings in chronological start order so freeing decisions are valid.
2
Lines 8-9Free a finished room
If the earliest-ending meeting is over by this start, pop it to reuse that room.
3
Lines 10Occupy a room
Push the current end; the net heap size reflects rooms in use, whose peak is the answer.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Single meeting needs one room
Meetings that only touch (e.g. [1,5] then [5,8]) can share a room
All meetings identical need n rooms
Fully nested meetings

Common beginner mistakes

Using < instead of <= when freeing, forcing an extra room for meetings that end exactly when the next begins
Sorting by end instead of start
Returning the last heap size correctly works here only because we never over-pop — but forgetting to guard the pop with 'if heap' crashes on the first meeting

Check your understanding

Why does the final heap size equal the maximum number of rooms rather than just the rooms used at the end?

Meeting Rooms II

Meeting Rooms II

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Intervals and Sweep Line