Where it runs
1. The problem
An office has shared meeting rooms. The day's meetings are [[0,30],[5,10],[15,20]], with times in minutes. How many rooms do you need so every meeting has one?
Merging from the last lesson won't help here. Take the meetings [0,30] and [5,10]. Merging turns them into one block, [0,30]. Yet from minute 5 to minute 10 both meetings are running, and they need two rooms. After the merge that count is gone.
So the question is this: how many meetings run at the same time at the busiest moment of the day? That number, the peak, is how many rooms you need. The same question comes up in other forms: "how many database connections were open at once" or "how many users were online in the same second".
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedmaxOverlap([[1, 4], [2, 5], [7, 9], [3, 6], [5, 8]])| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
|---|---|---|---|---|---|---|---|---|---|
| [1,4] | ■ | ■ | ■ | ■ | |||||
| [2,5] | ■ | ■ | ■ | ■ | |||||
| [7,9] | ■ | ■ | ■ | ||||||
| [3,6] | ■ | ■ | ■ | ■ | |||||
| [5,8] | ■ | ■ | ■ | ■ |
How many intervals are open at the busiest moment? Each interval is a row on the timeline.
Recognise it
Say these words and it is this pattern
- maximum number of overlapping meetings/intervals at once
- minimum rooms/resources needed
- busiest moment in time
- how many intervals cover a given point
- events happening at the same time
Looks similar, isn't
- Intervals: merge & insert
Merging keeps intervals whole and joins the ones that touch. A sweep forgets them and counts.
- Difference array
That is a sweep whose coordinates are array indices. It needs a small, dense range.
- Binary heap / priority queue
A heap holds the open intervals so you know which ends soonest. The counter only knows how many.
- Prefix sums
Prefix sums answer over fixed positions in an array. A sweep walks events in sorted order.
n intervals give 2n events, so O(n log n) for the sort. The walk itself is O(n).
On LeetCode
Problems that ask how many ranges are open at the busiest moment, or at a given moment. Turn each range into plus 1 at its start and minus 1 at its end, sort the events, and sweep with a counter.
A birth adds one and a death year takes one away, and the answer is the earliest year with the peak count.
The lesson's meeting rooms, except that ranges sharing an end point overlap here, so a start opens before an equal end closes.
After each booking, sweep all the start and end events again and return the peak.
With starts and ends sorted, the flowers in bloom on a day are the starts up to it minus the ends before it, both found by binary search.