Meeting Rooms II: Counting Peak Overlap with a Sweep Line
Solve Meeting Rooms II in O(n log n) by sorting start and end times separately and sweeping for peak concurrent meetings — with a worked JavaScript walkthrough.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
You run an office with a stack of meeting requests, each with a start and end time. How many conference rooms do you actually need so that no meeting ever gets bumped? The answer is not the total number of meetings — plenty of them happen at different times and can share a room. The answer is the maximum number of meetings that overlap at any single instant.
That reframing is the whole problem. Once you stop thinking about "rooms" and start thinking about "how many things are happening at once," a clean sweep-line algorithm falls out, and it runs in O(n log n) with a couple of integer counters.
The problem
Given an array of meeting intervals where intervals[i] = [start, end], return the minimum number of conference rooms required. A meeting occupies a room over the half-open interval [start, end) — a meeting that ends exactly when another begins does not conflict.
Input: intervals = [[0, 30], [5, 10], [15, 20]]
Output: 2
Why: [0,30] runs the whole time. [5,10] overlaps it, so at t=5 two meetings
are live -> 2 rooms. [15,20] also overlaps [0,30], but [5,10] has
already ended by then, so it reuses that freed room. Peak overlap = 2.The trap is assuming three meetings need three rooms. They don't — [5,10] finishes long before [15,20] starts, so those two never coexist and share a room. The count you want is the busiest moment, not the total.
The brute force baseline
The literal approach: for every meeting, count how many other meetings overlap it, and take the largest count.
function minMeetingRoomsBrute(intervals) {
let max = 0;
for (let i = 0; i < intervals.length; i++) {
let overlaps = 1; // the meeting overlaps itself
for (let j = 0; j < intervals.length; j++) {
if (i === j) continue;
// do meeting j and meeting i overlap?
if (intervals[j][0] < intervals[i][1] && intervals[i][0] < intervals[j][1]) {
overlaps++;
}
}
max = Math.max(max, overlaps);
}
return max;
}This is correct but wasteful. It compares every pair of meetings, so it's O(n²) time. Worse, it's subtly wrong about where peak overlap happens: counting overlaps against a single meeting's window isn't always the true global peak when meetings interleave in complicated ways. On top of being slow, it makes you reason about pairwise overlap instead of the one number you care about.
The key insight: sweep a line across sorted events
Forget the meetings as objects. A meeting is really two events: a +1 when it starts (a room gets taken) and a -1 when it ends (a room frees up). Lay all the start times and all the end times on a timeline, then walk left to right. Keep a running count of live meetings — increment on a start, decrement on an end. The highest that counter ever reaches is your answer.
Here's the clever part that makes it O(n log n) instead of needing a heap: you don't need to keep starts and ends paired. Sort all the start times into one array and all the end times into another. Then use two pointers, s and e, and repeatedly ask a single question:
Does the next meeting start before the earliest still-open meeting ends?
- If yes (
starts[s] < ends[e]): a meeting begins while another is still running. Overlap increases — allocate a room, advances. - If no: the earliest meeting ends before (or exactly when) the next one starts. A room frees up — advance
e.
Because both arrays are sorted, the earliest unprocessed start and earliest unprocessed end are always at the pointers. You never need to know which start pairs with which end — only which event comes first.
The optimal solution
This is the exact algorithm the visualizer steps through:
var minMeetingRooms = function (intervals) {
const starts = intervals.map((interval) => interval[0]).sort((a, b) => a - b);
const ends = intervals.map((interval) => interval[1]).sort((a, b) => a - b);
let s = 0, e = 0;
let rooms = 0, maxRooms = 0;
while (s < starts.length) {
if (starts[s] < ends[e]) {
rooms += 1; // a meeting starts before the earliest one ends
s += 1;
} else {
rooms -= 1; // the earliest meeting ends, freeing a room
e += 1;
}
maxRooms = Math.max(maxRooms, rooms);
}
return maxRooms;
};Two details carry the correctness. First, the comparison is strict <, which encodes the half-open [start, end) rule: a start at time t that equals an end at time t takes the else branch, so back-to-back meetings correctly reuse the room. Second, the loop condition is s < starts.length, not e < ends.length — once every start has been processed, no new overlap can appear, and maxRooms is already locked in. Trailing end events can't raise the peak, so there's no reason to keep sweeping them.
Walkthrough
Trace intervals = [[0, 30], [5, 10], [15, 20]]. After sorting: starts = [0, 5, 15], ends = [10, 20, 30].
| Step | s | e | starts[s] | ends[e] | starts[s] < ends[e]? | Action | rooms | maxRooms |
|---|---|---|---|---|---|---|---|---|
| init | 0 | 0 | 0 | 10 | — | — | 0 | 0 |
| 1 | 0 | 0 | 0 | 10 | 0 < 10 → yes | meeting starts, s→1 | 1 | 1 |
| 2 | 1 | 0 | 5 | 10 | 5 < 10 → yes | meeting starts, s→2 | 2 | 2 |
| 3 | 2 | 0 | 15 | 10 | 15 < 10 → no | meeting ends, e→1 | 1 | 2 |
| 4 | 2 | 1 | 15 | 20 | 15 < 20 → yes | meeting starts, s→3 | 2 | 2 |
| exit | 3 | 1 | — | — | s = 3, loop ends | return | — | 2 |
The story the table tells: two meetings pile up by step 2 (that's [0,30] and [5,10] both live at t=5), then at step 3 the sweep hits an end event before the next start — [5,10] closes at t=10, freeing its room. Step 4 opens [15,20] into that freed room, so the count climbs back to 2 but never exceeds the earlier peak. Final answer: 2 rooms.
Complexity
| Approach | Time | Space | Why |
|---|---|---|---|
| Brute force pairwise | O(n²) | O(1) | every meeting compared against every other |
| Min-heap of end times | O(n log n) | O(n) | sort by start, heap push/pop per meeting |
| Sweep two sorted arrays | O(n log n) | O(n) | two sorts dominate; the sweep is a single O(n) pass |
The two sort calls are the only super-linear work — everything after is a linear walk with O(1) work per event. Space is O(n) for the starts and ends copies. The heap solution has the same asymptotics, but the sorted-arrays sweep avoids the heap's constant-factor overhead and is easier to write correctly under interview pressure.
Common mistakes
- Returning the number of meetings. Three meetings can need one room or five rooms — the answer is peak concurrency, never the input length.
- Using
<=instead of<. With<=, a meeting ending at t=10 and one starting at t=10 would be counted as overlapping, inflating the room count. The half-open[start, end)semantics require strict<. - Sorting the intervals as pairs. The trick only works because starts and ends are sorted independently. Keeping them paired forces you back to a heap.
- Looping while
e < ends.length. After the last start is consumed,roomsonly ever decreases, somaxRoomscan't grow. Extending the loop over trailing ends does nothing but risk an index error. - Forgetting to update
maxRoomsafter every event. Update it inside the loop on each step, not just after a start — a clean pattern is to recompute the max unconditionally each iteration.
Where this pattern shows up next
The sweep-line-over-sorted-events idea and the sorted-array two-pointer scan behind it power a whole family of array problems:
- Best Time to Buy and Sell Stock — a single left-to-right sweep tracking a running best, the same "one pass, keep the peak" shape.
- Remove Duplicates from Sorted Array — two pointers walking a sorted array, deciding at each step whether to advance one or both.
- Remove Element — the read/write two-pointer variant on an unsorted array.
- Reverse String — the converging two-pointer template in its simplest form.
You can also step through Meeting Rooms II interactively to watch the sweep line cross the Gantt chart and the room counter rise and fall event by event.
FAQ
Why sort start times and end times separately?
Because you never need to know which end belongs to which start — you only need the earliest unprocessed event of each kind. Sorting both arrays puts those at the front, so two pointers can always compare "next meeting to start" against "earliest meeting to finish." Keeping intervals paired would force a heap to track live end times, which is more code and a larger constant factor for the same O(n log n).
What is the time and space complexity of Meeting Rooms II?
Time is O(n log n), dominated entirely by the two sort operations; the sweep itself is a single O(n) pass with constant work per event. Space is O(n) for the two sorted copies of start and end times. The naive pairwise-overlap approach is O(n²) time, which is why sorting first pays off on large inputs.
Why is the comparison strict less-than instead of less-than-or-equal?
Meetings occupy the half-open interval [start, end), meaning a meeting that ends at t=10 is done the instant t=10, so another meeting starting at t=10 can reuse the room. Strict starts[s] < ends[e] sends the equal case to the else branch (free a room), correctly treating back-to-back meetings as non-overlapping. Using <= would count them as simultaneous and overallocate rooms.
Can I solve Meeting Rooms II with a min-heap instead?
Yes, and it's a common alternative. Sort meetings by start time, then keep a min-heap of the end times of currently-running meetings. For each meeting, pop any end time that is less than or equal to the current start (those rooms freed up), then push the current meeting's end. The heap's size at its largest is the answer. It's the same O(n log n) time and O(n) space, but the two-sorted-arrays sweep is usually faster to write bug-free.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.