Loading…

mediumIntervalsLC #253Asked very often

Meeting Rooms II

Q: How do you solve Meeting Rooms II using the Min-Heap of End Times approach?

When to use it: The most intuitive optimal — say 'a min-heap of end times is my pool of in-use rooms; the top is the one that frees soonest'. Sort the meetings by start time, then process them in that order while maintaining a min-heap of the end times of meetings that currently hold a room. **Why a min-heap of end times.** When a new meeting starts, the only question is: *has any room freed up by now?* The room that frees the earliest is the one whose meeting ends soonest — exactly the minimum end time. A min-heap keyed on end time keeps that value on top in O(1), and removing it is O(log n). So for each meeting we peek the top: if `heap.top() <= newStart`, that room is free, pop it (we'll immediately reuse it). Then push the current meeting's end time regardless. If no room was free, we didn't pop, so the heap grew — that's a newly allocated room. **Why the heap size IS the room count.** Every element in the heap is a meeting currently occupying a room. We pop at most one per step (a single room frees per arriving meeting in this formulation) and push exactly one, so the heap size at any moment equals the number of rooms in use at that time. The maximum it ever reaches is the peak concurrency — the minimum rooms required. **Why `<=` and not `<` for reuse.** A room frees the instant its meeting ends. If the previous meeting ends exactly when the new one starts, the room is available — back-to-back is allowed — so the reuse condition is `end <= newStart`. Time complexity: O(n log n). Space complexity: O(n).

Q: How do you solve Meeting Rooms II using the Chronological Sweep — Two Sorted Arrays (Optimal) approach?

When to use it: Offer as the slick alternative: 'separate starts and ends, sort each, and sweep a running room counter'. Decouple starts from ends. Build two arrays — all start times sorted, and all end times sorted — then sweep through time with two pointers. **The +1/−1 mental model.** Picture walking a timeline. Every meeting start is a `+1` event (a room becomes occupied); every meeting end is a `−1` event (a room frees). The number of rooms in use at any instant is the running sum of these events in chronological order, and the answer is the maximum that running sum ever reaches. We don't need to know *which* meeting started or ended — only the net concurrency. **Why two sorted arrays and not paired intervals.** A start and an end are independent events on the timeline, so we sort them independently. The start pointer `s` and end pointer `e` always point at the next upcoming start and next upcoming end. Compare them: if `starts[s] < ends[e]`, the next thing to happen is a meeting beginning, so `rooms++` and advance `s`. Otherwise the next thing is a meeting ending (or a simultaneous end that frees a room for the start), so `rooms--` and advance `e`. Track `max(rooms)`. **Why `starts[s] < ends[e]` with strict `<`.** When a start and an end coincide (`start == end`), the room frees exactly as the new meeting begins — back-to-back reuse — so we should treat it as an end first (no new room). Strict `<` on the start side does exactly that: ties fall through to the `else` branch and decrement, letting the freed room be reused. **Why this is the clean optimal.** Same O(n log n) as the heap, but the inner loop is just integer comparisons and increments — no heap operations, smaller constant, and arguably the easiest to get right once you see the +1/−1 framing. Time complexity: O(n log n). Space complexity: O(n).

LCPractice

Intervals · 5 of 7 · 9 min

Given an array of meeting time intervals intervals where intervals[i] = [startᵢ, endᵢ], return the minimum number of conference rooms required so that all meetings can be held.

A room can be reused once a meeting finishes: a meeting ending at time t frees its room for another meeting starting at time t (back-to-back is allowed).

In plain English

You're scheduling meetings into rooms. Two meetings that overlap in time can't share a room, so at the busiest instant you need as many rooms as there are meetings running at once. Find that peak — that's the minimum number of rooms.

Examples

Example 1

Input: intervals = [[0,30],[5,10],[15,20]]
Output: 2
Note: [0,30] overlaps both [5,10] and [15,20], but those two don't overlap each other. Peak concurrency is 2 (during [5,10] and during [15,20], [0,30] is also running).

Example 2

Input: intervals = [[7,10],[2,4]]
Output: 1
Note: They don't overlap, so one room suffices — the second meeting reuses the room after the first.

Example 3

Input: intervals = [[1,5],[2,6],[3,7]]
Output: 3
Note: All three are simultaneously active around time 3–5, so peak concurrency is 3.

Constraints

1 ≤ intervals.length ≤ 10⁴
intervals[i].length == 2
0 ≤ startᵢ < endᵢ ≤ 10⁶
A room can be reused starting exactly at the time the previous meeting ended

Clarifying questions4First question: Can a room be reused the moment a meeting ends?Explore questions

Q1.Can a room be reused the moment a meeting ends?
Yes — a meeting ending at t and one starting at t can share a room. So the 'is a room free?' test uses <= (end ≤ newStart).
Q2.Is the input sorted?
No. I'll sort by start (and for the sweep, also have ends sorted) — ordering by time is what makes this tractable.
Q3.Do I return the count of rooms or an assignment of meetings to rooms?
Just the minimum count. The heap naturally yields it as the peak number of rooms in use.
Q4.Are meeting times integers and bounded?
Yes — small enough that sorting is the bottleneck; no need for a coordinate-compression trick.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

The minimum number of rooms equals the maximum number of meetings happening at the same instant — the peak concurrency. Sort by start, keep a min-heap of the end times of meetings currently using a room; for each new meeting, if the earliest-ending room has freed up (its end ≤ new start) reuse it, otherwise allocate a new room. The heap's max size is the answer. O(n log n).

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you reframe 'minimum rooms' as 'maximum simultaneous meetings' and use a min-heap of end times (or a sweep) to track peak concurrency, instead of trying to merge or pair-check.

Where candidates slip

Trying to merge intervals (that counts disjoint groups, not concurrency), or comparing the new meeting against the wrong room — you must check the room that frees EARLIEST, which is exactly the heap top.

How to stand out

State 'rooms = peak overlap' upfront, justify the min-heap as 'the soonest-available room', use <= for back-to-back reuse, and offer the two-pointer sweep over sorted start/end arrays as an equivalent O(n log n) with a cleaner constant.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Min-Heap of End Times	`O(n log n)`	`O(n)`	The most intuitive optimal — say 'a min-heap of end times is my pool of in-use rooms; the top is the one that frees soonest'.	Read
2	Chronological Sweep — Two Sorted Arrays (Optimal)Optimal	`O(n log n)`	`O(n)`	Offer as the slick alternative: 'separate starts and ends, sort each, and sweep a running room counter'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewQuestion about overlapping meetingsBoolean, merge, or count rooms?Can one attend all?Merge overlapsExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Min-Heap of End Times

TimeO(n log n)SpaceO(n)

The most intuitive optimal — say 'a min-heap of end times is my pool of in-use rooms; the top is the one that frees soonest'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Reframe: the number of rooms you need is the largest number of meetings overlapping at any single moment. How do you track that as you scan in time order?

2Hint 2Explore hint

Sort by start. Keep a min-heap of the end times of meetings currently occupying rooms.

3Hint 3Explore hint

For each new meeting, if the smallest end time in the heap is ≤ its start, a room freed — pop it. Always push the new end. The heap size is the rooms in use; its peak is the answer.

A · Core idea

Sort the meetings by start time, then process them in that order while maintaining a min-heap of the end times of meetings that currently hold a room.

Why a min-heap of end times. When a new meeting starts, the only question is: has any room freed up by now? The room that frees the earliest is the one whose meeting ends soonest — exactly the minimum end time. A min-heap keyed on end time keeps that value on top in O(1), and removing it is O(log n). So for each meeting we peek the top: if heap.top() <= newStart, that room is free, pop it (we'll immediately reuse it). Then push the current meeting's end time regardless. If no room was free, we didn't pop, so the heap grew — that's a newly allocated room.

Why the heap size IS the room count. Every element in the heap is a meeting currently occupying a room. We pop at most one per step (a single room frees per arriving meeting in this formulation) and push exactly one, so the heap size at any moment equals the number of rooms in use at that time. The maximum it ever reaches is the peak concurrency — the minimum rooms required.

Why `<=` and not `<` for reuse. A room frees the instant its meeting ends. If the previous meeting ends exactly when the new one starts, the room is available — back-to-back is allowed — so the reuse condition is end <= newStart.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

intervals = [[0,30],[5,10],[15,20]] (sorted by start: same)

Array state

[0,30]

push 30 → 1 room

[0]

Current pointerResolved stateNot processed

Final resultmax heap size = 2

C · Code with teaching comments

Reference implementation previewpublic int minMeetingRooms(int[][] intervals) { Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0])); PriorityQueue<Integer> heap = new PriorityQueue<>(); int peak = 0; for (int[] iv : intervals) {Explore the full code

solution.javaJava

Min-Heap of End Times — reference

4 teaching notes

1
public int minMeetingRooms(int[][] intervals) {
2
    // Process meetings in start order so the heap reflects what's running 'now'.
3
    Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
4
    PriorityQueue<Integer> heap = new PriorityQueue<>();
5
    int peak = 0;
6
    for (int[] iv : intervals) {
7
        // Soonest-freeing room's end ≤ this start → that room is free, reuse it.
8
        if (!heap.isEmpty() && heap.peek() <= iv[0]) {
9
            heap.poll();
10
        }
11
        // This meeting now occupies a room (reused or new) until its end time.
12
        heap.offer(iv[1]);
13
        // Rooms in use right now = heap size; the running max is the answer.
14
        peak = Math.max(peak, heap.size());
15
    }
16
    return peak;
17
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.17 lines

D · Why it works and complexityO(n log n) timeO(n) spaceOpen the invariant and proofExplore the proof

The heap is a live 'pool of busy rooms', and the min-heap discipline means you always test against the room that becomes available first — testing any other room would be strictly worse. This 'keep the resource that frees soonest on top' idea is the heart of countless scheduling problems (CPU task scheduling, k-way merge, Single-Threaded CPU). Once 'min rooms = peak overlap' clicks, the heap is just the bookkeeping.

ComplexityO(n log n) time, O(n) space — Sorting is O(n log n); each meeting does O(log n) heap work (one push, at most one pop), so the scan is O(n log n). The heap holds at most n end times → O(n) space.

E · Edge cases and pitfalls5intervals = [[1,5],[2,6],[3,7]] — No top ever ≤ next start, so we push without popping each time → heap grows to 3 → returns 3.Explore edge cases

Edge cases handled

intervals = [[1,5],[2,6],[3,7]]No top ever ≤ next start, so we push without popping each time → heap grows to 3 → returns 3.
intervals = [[0,30],[30,60]]Second meeting: top 30 ≤ 30 → reuse the room → heap size stays 1 → returns 1.

Pitfalls

Using a max-heap or a heap of starts — you must surface the SOONEST-freeing room (min end).
Using `<` for reuse — a room freeing exactly at the new start should be reusable, so use `<=`.
Reporting the final heap size without tracking the peak (works in this one-pop-per-push form, but track peak to be safe).

03.2

Approach 2 of 2 · Optimal

Chronological Sweep — Two Sorted Arrays (Optimal)

TimeO(n log n)SpaceO(n)

Offer as the slick alternative: 'separate starts and ends, sort each, and sweep a running room counter'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Forget about which room — just track how the count of active meetings rises and falls over time.

2Hint 2Explore hint

Split the intervals into a sorted array of start times and a sorted array of end times.

3Hint 3Explore hint

Walk both with two pointers: if the next start is before the next end, a meeting begins (rooms++); otherwise one ended (rooms--, advance the end pointer). Track the max rooms.

A · Core idea

Decouple starts from ends. Build two arrays — all start times sorted, and all end times sorted — then sweep through time with two pointers.

The +1/−1 mental model. Picture walking a timeline. Every meeting start is a +1 event (a room becomes occupied); every meeting end is a −1 event (a room frees). The number of rooms in use at any instant is the running sum of these events in chronological order, and the answer is the maximum that running sum ever reaches. We don't need to know which meeting started or ended — only the net concurrency.

Why two sorted arrays and not paired intervals. A start and an end are independent events on the timeline, so we sort them independently. The start pointer s and end pointer e always point at the next upcoming start and next upcoming end. Compare them: if starts[s] < ends[e], the next thing to happen is a meeting beginning, so rooms++ and advance s. Otherwise the next thing is a meeting ending (or a simultaneous end that frees a room for the start), so rooms-- and advance e. Track max(rooms).

Why `starts[s] < ends[e]` with strict `<`. When a start and an end coincide (start == end), the room frees exactly as the new meeting begins — back-to-back reuse — so we should treat it as an end first (no new room). Strict < on the start side does exactly that: ties fall through to the else branch and decrement, letting the freed room be reused.

Why this is the clean optimal. Same O(n log n) as the heap, but the inner loop is just integer comparisons and increments — no heap operations, smaller constant, and arguably the easiest to get right once you see the +1/−1 framing.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

intervals = [[0,30],[5,10],[15,20]]

Array state

start 0

no end ≤ 0 → rooms=1

s ↓

[0]

[1]

[2]

Current pointerResolved stateNot processed

Final resultmax rooms = 2

C · Code with teaching comments

solution.javaJava

Chronological Sweep — Two Sorted Arrays (Optimal) — optimal

4 teaching notes

1
public int minMeetingRooms(int[][] intervals) {
2
    int n = intervals.length;
3
    int[] starts = new int[n], ends = new int[n];
4
    for (int i = 0; i < n; i++) {
5
        starts[i] = intervals[i][0];
6
        ends[i] = intervals[i][1];
7
    }
8
    // Starts and ends are independent timeline events, sorted separately.
9
    Arrays.sort(starts);
10
    Arrays.sort(ends);
11
    int rooms = 0, peak = 0, e = 0;
12
    for (int s = 0; s < n; s++) {
13
        // Every meeting that ended at or before this start frees a room first (<= =
14
        // back-to-back reuse).
15
        while (ends[e] <= starts[s]) {
16
            // Each freed meeting releases a room before we seat the new one.
17
            rooms--;
18
            e++;
19
        }
20
        // This start occupies a room; peak of `rooms` over time is the answer.
21
        rooms++;
22
        peak = Math.max(peak, rooms);
23
    }
24
    return peak;
25
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.25 lines

D · Why it works and complexityO(n log n) timeO(n) spaceOpen the invariant and proofExplore the proof

This is the sweep-line technique in its purest form: replace objects (intervals) with their boundary events (+1 starts, −1 ends), sort the events, and the running balance is your live quantity of interest — here, rooms in use. The heap and the sweep compute the identical peak; the sweep just makes 'peak overlap' literal. Recognizing 'max running balance over sorted events' generalizes to car-pooling, my-calendar, and CPU-load problems.

ComplexityO(n log n) time, O(n) space — Two sorts of n elements are O(n log n) and dominate; the two-pointer sweep is O(n). Two arrays of size n → O(n) space.

E · Edge cases and pitfalls5intervals = [[7,10],[2,4]] — starts=[2,7], ends=[4,10]. start 2 → rooms 1; start 7: end 4 ≤ 7 frees → rooms 0 then 1 → peak 1.Explore edge cases

Edge cases handled

intervals = [[7,10],[2,4]]starts=[2,7], ends=[4,10]. start 2 → rooms 1; start 7: end 4 ≤ 7 frees → rooms 0 then 1 → peak 1.
intervals = [[1,5],[2,6],[3,7]]No end ≤ the next start until all three are seated → rooms climbs 1→2→3 → peak 3.

Pitfalls

Pairing starts with their own ends — they must be sorted independently as separate event streams.
Using `<` instead of `<=` when freeing rooms — would refuse back-to-back reuse and overcount rooms.
Returning the final `rooms` instead of the running peak — the max can occur mid-sweep.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int minMeetingRooms(int[][] intervals) { int n = intervals.length; int[] starts = new int[n], ends = new int[n]; for (int i = 0; i < n; i++) { starts[i] = intervals[i][0];Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Merging intervals instead of counting overlap

Merge Intervals collapses overlapping ranges into groups, but a single merged group can contain 3 simultaneous meetings. The room count is peak concurrency, not the number of merged groups.

Explore the code comparison

Don't write this

merged = merge(intervals)
return len(merged)            # counts clusters, not concurrency

Write this instead

heap = []
for s, e in sorted(intervals):
    if heap and heap[0] <= s: heapq.heappop(heap)
    heapq.heappush(heap, e)
return len(heap)              # peak concurrency

Comparing against the wrong room

Only the room that frees EARLIEST matters — if even that one is still busy, every room is busy and you need a new one. That's why the min-heap top (smallest end) is the right thing to test.

Explore the code comparison

Don't write this

// checks the most-recently-added end, not the soonest-freeing
if (lastEnd <= iv[0]) reuseRoom();

Write this instead

if (!heap.isEmpty() && heap.peek() <= iv[0]) heap.poll(); // soonest-freeing
heap.offer(iv[1]);

Strict inequality blocks back-to-back reuse

A room freeing exactly when the next meeting starts can be reused. Using < instead of <= forces an unnecessary extra room when end == newStart.

Explore the code comparison

Don't write this

if heap and heap[0] < s:      # refuses reuse at end == start
    heapq.heappop(heap)

Write this instead

if heap and heap[0] <= s:     # back-to-back reuse allowed
    heapq.heappop(heap)

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Max concurrency via min-heap of end times (or chronological sweep)

Code pattern to memorize

sort by start
heap = []  # end times of in-use rooms
for s, e in meetings:
    if heap and heap[0] <= s: heappop(heap)   # a room freed
    heappush(heap, e)
return len(heap)  # peak size

Rules to remember

1Rooms needed = peak number of simultaneously-active meetings. Translate the whole problem to 'max overlap at any instant'.
2Sort by start, and let the min-heap hold end times so the soonest-freeing room is always on top.
3Reuse test is heap.top() <= newStart (with <=: a room freeing exactly when the next starts can be reused).
4The answer is the maximum heap size reached (equivalently the final size if you only pop one per push) — track the peak.
5Alternative: split into sorted starts[] and sorted ends[], sweep with two pointers; room++ on a start before the next end, room-- otherwise.

Use this pattern when

'Minimum rooms / servers / machines to handle all intervals'
Maximum number of overlapping intervals at any point
Resource-allocation where each concurrent task needs its own unit
Peak-load / max-concurrency questions on time ranges

Choose another pattern when

'Can ONE person attend all?' → boolean adjacent-overlap check (LC 252)
'Merge the overlaps' → sort by start, sweep-merge (LC 56)
'Remove fewest to make disjoint' → greedy by end (LC 435)
You need WHICH room each meeting uses, not just the count → assign heap entries to room ids

Interview takeaway

Minimum rooms = maximum concurrent meetings — reframing 'allocation' as 'peak overlap' is the unlock. A min-heap of end times tells you in O(log n) whether any room has freed up; the chronological two-array sweep computes the same peak as a running +1/−1 balance.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternPeak-Concurrency Sweep. Minimum resources = maximum simultaneous intervals. A min-heap of end times or a sorted-events +1/−1 sweep both yield the peak — the template for Car Pooling and My Calendar.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Meeting Rooms
The boolean version — can one room hold all? Adjacent-overlap check after sorting.
Car Pooling
Coming soon
Same +1/−1 sweep, but events carry passenger counts and the cap is fixed capacity.
My Calendar II
Coming soon
Reject a booking that would push concurrency past 2 — overlap counting online.
Merge Intervals
Contrast: merging counts disjoint groups, not concurrent overlap.

Same pattern

←

Meeting Rooms

Continue · Next problem

Minimum Number of Arrows to Burst Balloons

mediumIntervalsLC #253Asked very often

Meeting Rooms II

LCPractice

Intervals · 5 of 7 · 9 min

Given an array of meeting time intervals intervals where intervals[i] = [startᵢ, endᵢ], return the minimum number of conference rooms required so that all meetings can be held.

A room can be reused once a meeting finishes: a meeting ending at time t frees its room for another meeting starting at time t (back-to-back is allowed).

In plain English

Examples

Example 1

Input: intervals = [[0,30],[5,10],[15,20]]
Output: 2
Note: [0,30] overlaps both [5,10] and [15,20], but those two don't overlap each other. Peak concurrency is 2 (during [5,10] and during [15,20], [0,30] is also running).

Example 2

Input: intervals = [[7,10],[2,4]]
Output: 1
Note: They don't overlap, so one room suffices — the second meeting reuses the room after the first.

Example 3

Input: intervals = [[1,5],[2,6],[3,7]]
Output: 3
Note: All three are simultaneously active around time 3–5, so peak concurrency is 3.

Constraints

1 ≤ intervals.length ≤ 10⁴
intervals[i].length == 2
0 ≤ startᵢ < endᵢ ≤ 10⁶
A room can be reused starting exactly at the time the previous meeting ended

Clarifying questions4First question: Can a room be reused the moment a meeting ends?Explore questions

Q1.Can a room be reused the moment a meeting ends?
Yes — a meeting ending at t and one starting at t can share a room. So the 'is a room free?' test uses <= (end ≤ newStart).
Q2.Is the input sorted?
No. I'll sort by start (and for the sweep, also have ends sorted) — ordering by time is what makes this tractable.
Q3.Do I return the count of rooms or an assignment of meetings to rooms?
Just the minimum count. The heap naturally yields it as the peak number of rooms in use.
Q4.Are meeting times integers and bounded?
Yes — small enough that sorting is the bottleneck; no need for a coordinate-compression trick.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you reframe 'minimum rooms' as 'maximum simultaneous meetings' and use a min-heap of end times (or a sweep) to track peak concurrency, instead of trying to merge or pair-check.

Where candidates slip

How to stand out

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Min-Heap of End Times	`O(n log n)`	`O(n)`	The most intuitive optimal — say 'a min-heap of end times is my pool of in-use rooms; the top is the one that frees soonest'.	Read
2	Chronological Sweep — Two Sorted Arrays (Optimal)Optimal	`O(n log n)`	`O(n)`	Offer as the slick alternative: 'separate starts and ends, sort each, and sweep a running room counter'.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Min-Heap of End Times

TimeO(n log n)SpaceO(n)

The most intuitive optimal — say 'a min-heap of end times is my pool of in-use rooms; the top is the one that frees soonest'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Reframe: the number of rooms you need is the largest number of meetings overlapping at any single moment. How do you track that as you scan in time order?

2Hint 2Explore hint

Sort by start. Keep a min-heap of the end times of meetings currently occupying rooms.

3Hint 3Explore hint

For each new meeting, if the smallest end time in the heap is ≤ its start, a room freed — pop it. Always push the new end. The heap size is the rooms in use; its peak is the answer.

A · Core idea

Sort the meetings by start time, then process them in that order while maintaining a min-heap of the end times of meetings that currently hold a room.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

intervals = [[0,30],[5,10],[15,20]] (sorted by start: same)

Array state

[0,30]

push 30 → 1 room

[0]

Current pointerResolved stateNot processed

Final resultmax heap size = 2

C · Code with teaching comments

solution.javaJava

Min-Heap of End Times — reference

4 teaching notes

1
public int minMeetingRooms(int[][] intervals) {
2
    // Process meetings in start order so the heap reflects what's running 'now'.
3
    Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
4
    PriorityQueue<Integer> heap = new PriorityQueue<>();
5
    int peak = 0;
6
    for (int[] iv : intervals) {
7
        // Soonest-freeing room's end ≤ this start → that room is free, reuse it.
8
        if (!heap.isEmpty() && heap.peek() <= iv[0]) {
9
            heap.poll();
10
        }
11
        // This meeting now occupies a room (reused or new) until its end time.
12
        heap.offer(iv[1]);
13
        // Rooms in use right now = heap size; the running max is the answer.
14
        peak = Math.max(peak, heap.size());
15
    }
16
    return peak;
17
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.17 lines

D · Why it works and complexityO(n log n) timeO(n) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls5intervals = [[1,5],[2,6],[3,7]] — No top ever ≤ next start, so we push without popping each time → heap grows to 3 → returns 3.Explore edge cases

Edge cases handled

intervals = [[1,5],[2,6],[3,7]]No top ever ≤ next start, so we push without popping each time → heap grows to 3 → returns 3.
intervals = [[0,30],[30,60]]Second meeting: top 30 ≤ 30 → reuse the room → heap size stays 1 → returns 1.

Pitfalls

Using a max-heap or a heap of starts — you must surface the SOONEST-freeing room (min end).
Using `<` for reuse — a room freeing exactly at the new start should be reusable, so use `<=`.
Reporting the final heap size without tracking the peak (works in this one-pop-per-push form, but track peak to be safe).

03.2

Approach 2 of 2 · Optimal

Chronological Sweep — Two Sorted Arrays (Optimal)

TimeO(n log n)SpaceO(n)

Offer as the slick alternative: 'separate starts and ends, sort each, and sweep a running room counter'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Forget about which room — just track how the count of active meetings rises and falls over time.

2Hint 2Explore hint

Split the intervals into a sorted array of start times and a sorted array of end times.

3Hint 3Explore hint

Walk both with two pointers: if the next start is before the next end, a meeting begins (rooms++); otherwise one ended (rooms--, advance the end pointer). Track the max rooms.

A · Core idea

Decouple starts from ends. Build two arrays — all start times sorted, and all end times sorted — then sweep through time with two pointers.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

intervals = [[0,30],[5,10],[15,20]]

Array state

start 0

no end ≤ 0 → rooms=1

s ↓

[0]

[1]

[2]

Current pointerResolved stateNot processed

Final resultmax rooms = 2

C · Code with teaching comments

solution.javaJava

Chronological Sweep — Two Sorted Arrays (Optimal) — optimal

4 teaching notes

1
public int minMeetingRooms(int[][] intervals) {
2
    int n = intervals.length;
3
    int[] starts = new int[n], ends = new int[n];
4
    for (int i = 0; i < n; i++) {
5
        starts[i] = intervals[i][0];
6
        ends[i] = intervals[i][1];
7
    }
8
    // Starts and ends are independent timeline events, sorted separately.
9
    Arrays.sort(starts);
10
    Arrays.sort(ends);
11
    int rooms = 0, peak = 0, e = 0;
12
    for (int s = 0; s < n; s++) {
13
        // Every meeting that ended at or before this start frees a room first (<= =
14
        // back-to-back reuse).
15
        while (ends[e] <= starts[s]) {
16
            // Each freed meeting releases a room before we seat the new one.
17
            rooms--;
18
            e++;
19
        }
20
        // This start occupies a room; peak of `rooms` over time is the answer.
21
        rooms++;
22
        peak = Math.max(peak, rooms);
23
    }
24
    return peak;
25
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.25 lines

D · Why it works and complexityO(n log n) timeO(n) spaceOpen the invariant and proofExplore the proof

ComplexityO(n log n) time, O(n) space — Two sorts of n elements are O(n log n) and dominate; the two-pointer sweep is O(n). Two arrays of size n → O(n) space.

E · Edge cases and pitfalls5intervals = [[7,10],[2,4]] — starts=[2,7], ends=[4,10]. start 2 → rooms 1; start 7: end 4 ≤ 7 frees → rooms 0 then 1 → peak 1.Explore edge cases

Edge cases handled

intervals = [[7,10],[2,4]]starts=[2,7], ends=[4,10]. start 2 → rooms 1; start 7: end 4 ≤ 7 frees → rooms 0 then 1 → peak 1.
intervals = [[1,5],[2,6],[3,7]]No end ≤ the next start until all three are seated → rooms climbs 1→2→3 → peak 3.

Pitfalls

Pairing starts with their own ends — they must be sorted independently as separate event streams.
Using `<` instead of `<=` when freeing rooms — would refuse back-to-back reuse and overcount rooms.
Returning the final `rooms` instead of the running peak — the max can occur mid-sweep.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Merging intervals instead of counting overlap

Merge Intervals collapses overlapping ranges into groups, but a single merged group can contain 3 simultaneous meetings. The room count is peak concurrency, not the number of merged groups.

Explore the code comparison

Don't write this

merged = merge(intervals)
return len(merged)            # counts clusters, not concurrency

Write this instead

heap = []
for s, e in sorted(intervals):
    if heap and heap[0] <= s: heapq.heappop(heap)
    heapq.heappush(heap, e)
return len(heap)              # peak concurrency

Comparing against the wrong room

Only the room that frees EARLIEST matters — if even that one is still busy, every room is busy and you need a new one. That's why the min-heap top (smallest end) is the right thing to test.

Explore the code comparison

Don't write this

// checks the most-recently-added end, not the soonest-freeing
if (lastEnd <= iv[0]) reuseRoom();

Write this instead

if (!heap.isEmpty() && heap.peek() <= iv[0]) heap.poll(); // soonest-freeing
heap.offer(iv[1]);

Strict inequality blocks back-to-back reuse

A room freeing exactly when the next meeting starts can be reused. Using < instead of <= forces an unnecessary extra room when end == newStart.

Explore the code comparison

Don't write this

if heap and heap[0] < s:      # refuses reuse at end == start
    heapq.heappop(heap)

Write this instead

if heap and heap[0] <= s:     # back-to-back reuse allowed
    heapq.heappop(heap)

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Max concurrency via min-heap of end times (or chronological sweep)

Code pattern to memorize

sort by start
heap = []  # end times of in-use rooms
for s, e in meetings:
    if heap and heap[0] <= s: heappop(heap)   # a room freed
    heappush(heap, e)
return len(heap)  # peak size

Rules to remember

1Rooms needed = peak number of simultaneously-active meetings. Translate the whole problem to 'max overlap at any instant'.
2Sort by start, and let the min-heap hold end times so the soonest-freeing room is always on top.
3Reuse test is heap.top() <= newStart (with <=: a room freeing exactly when the next starts can be reused).
4The answer is the maximum heap size reached (equivalently the final size if you only pop one per push) — track the peak.
5Alternative: split into sorted starts[] and sorted ends[], sweep with two pointers; room++ on a start before the next end, room-- otherwise.

Use this pattern when

'Minimum rooms / servers / machines to handle all intervals'
Maximum number of overlapping intervals at any point
Resource-allocation where each concurrent task needs its own unit
Peak-load / max-concurrency questions on time ranges

Choose another pattern when

'Can ONE person attend all?' → boolean adjacent-overlap check (LC 252)
'Merge the overlaps' → sort by start, sweep-merge (LC 56)
'Remove fewest to make disjoint' → greedy by end (LC 435)
You need WHICH room each meeting uses, not just the count → assign heap entries to room ids

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Meeting Rooms
The boolean version — can one room hold all? Adjacent-overlap check after sorting.
Car Pooling
Coming soon
Same +1/−1 sweep, but events carry passenger counts and the cap is fixed capacity.
My Calendar II
Coming soon
Reject a booking that would push concurrency past 2 — overlap counting online.
Merge Intervals
Contrast: merging counts disjoint groups, not concurrent overlap.

Same pattern

←

Meeting Rooms

Continue · Next problem

Minimum Number of Arrows to Burst Balloons