March 24
Meeting Rooms II
How to find how many meetings are active at the same time by tracking starts and ends in order.
Intervals Intermediate 20 min TypeScript
Given an array of meeting intervals intervals, where each item represents the start and end of one meeting, return the minimum number of rooms needed to hold all meetings.
If one meeting ends at the exact time another starts, the room can be reused.
Example:
Input: intervals = [[0,30],[5,10],[15,20]]
Output: 2
What to notice before coding
- The problem is about how many meetings overlap at the same time.
- It does not matter which room got which meeting. It only matters how many stay occupied together.
- After sorting, the earliest active ending time is the most important reference.
Common mistakes
- treating `[0,10]` and `[10,20]` as if they still overlap
- comparing each meeting against every room ever used even after sorting
Step 1 - Translate what the answer really measures
The question is not:
- "how do I distribute meetings into rooms?"
The question is:
- "what is the largest number of meetings active at the same time?"
That is the minimum number of rooms.
Step 2 - Write the most direct baseline
A natural baseline is:
- sort by start time
- keep a list with the ending time of each room in use
- for each meeting, linearly search for a free room
It works.
But when many rooms are active, it compares too much.
Step 3 - Ask which comparison really matters
To know whether some room can be reused, you do not need to inspect all of them.
You need to know:
- what is the smallest ending time among the occupied rooms?
If even that room is not free yet, none of the others are.
Step 4 - Turn that into sweep line
A clean way to do it is separating:
- all starts
- all ends
Then you walk through starts in order and free rooms whenever the earliest end already passed.
The maximum number of simultaneous meetings becomes the answer.
The interactive editor needs JavaScript. You can still read the prompt and copy the starter code below.
Starter code
export function minMeetingRooms(intervals: number[][]): number {
// your solution here
return 0
}
Haven't solved it yet?
Viewing the solution now may reduce learning. It's worth trying a bit more.
Open the reference solution
Without JavaScript, the reference solution is shown inline instead of in a dialog.
Solution
Final complexity
Time: O(n log n)
Space: O(n)
Solution 1 - Search for a free room by scanning end times toward O(n²)
Good baseline because it makes the cost of testing each room one by one visible.
export function minMeetingRooms(intervals: number[][]): number {
if (intervals.length === 0) {
return 0
}
const sorted = [...intervals].sort((a, b) => a[0] - b[0])
const roomEndTimes: number[] = []
for (const [start, end] of sorted) {
let assigned = false
for (let index = 0; index < roomEndTimes.length; index += 1) {
if (roomEndTimes[index] <= start) {
roomEndTimes[index] = end
assigned = true
break
}
}
if (!assigned) {
roomEndTimes.push(end)
}
}
return roomEndTimes.length
}It works, but the linear search for a free room repeats too many comparisons and can drift toward O(n²).
Solution 2 - Sweep line with sorted starts and ends in O(n log n)
Now the question becomes more focused: how many meetings are active right now?
export function minMeetingRooms(intervals: number[][]): number {
if (intervals.length === 0) {
return 0
}
const starts = intervals.map(([start]) => start).sort((a, b) => a - b)
const ends = intervals.map(([, end]) => end).sort((a, b) => a - b)
let endIndex = 0
let activeRooms = 0
let maxRooms = 0
for (const start of starts) {
while (endIndex < ends.length && ends[endIndex] <= start) {
activeRooms -= 1
endIndex += 1
}
activeRooms += 1
maxRooms = Math.max(maxRooms, activeRooms)
}
return maxRooms
}The strong insight here is that you do not need to model room assignments in detail. You only need to track how many are still occupied.
Another common version uses a heap to keep the earliest ending room at the top. Same underlying idea: the smallest active end is the only one you really need to inspect first.
What to say in the interview
A strong short explanation would be:
The problem asks for the peak number of simultaneous meetings. The baseline tries to fit each meeting into some free room and ends up scanning many rooms. The better version separates sorted starts and ends. When a start arrives, I free every meeting whose end already passed, then count the new meeting as active. The maximum number of active meetings during that sweep is the minimum number of rooms, and the total cost stays in
O(n log n)because of the sorting step.
That shows that you:
- translated the question into simultaneous overlaps
- avoided unnecessary modeling
- justified the sort and the linear sweep
When this pattern shows up again
This pattern comes back when you need to:
- count active intervals at the same time
- use sweep line instead of total comparison
- distinguish immediate reuse from real overlap
- solve minimum capacity problems over schedules, queues, and time windows
The point is not memorizing
Meeting Rooms II.
The point is learning how to read intervals as entry and exit events.