Meeting Rooms II
MediumIntervals
You get a list of meetings, each written as [start, end], in no particular order. Return the fewest rooms needed to hold all of them, when two meetings that overlap cannot share a room.
A room is free again the moment its meeting ends, so a meeting from 4 to 9 and one from 9 to 12 can use the same room.
Examples
Input: intervals = [[1, 5], [2, 6], [7, 9]] Output: 2
1 to 5 and 2 to 6 run at once. By 7 both are over, so the last one reuses a room.
Input: intervals = [[4, 9], [9, 12]] Output: 1
The second meeting starts as the first one ends.
Constraints
0 ≤ intervals.length ≤ 10⁴0 ≤ start < end ≤ 10⁶
Stuck?
Hint 1
The answer is the largest number of meetings going on at the same moment.
Hint 2
Sort the start times and the end times separately and walk both with two pointers: a start before the next end needs another room, otherwise a room frees up. A min-heap of end times works too.
The idea
The answer is the most meetings going on at the same moment. At each start you only need to know how many meetings have already ended, not which ones. So sort the start times and the end times separately, and walk through both in time order.
Time O(n log n)Extra space O(n)
Try it again with the idea in mind, or go through the code one step at a time.
The code, step by step
Step 1 of 5
Split the meetings into a sorted list of starts and a sorted list of ends. Pairing a start with its own end no longer matters: a freed room is a freed room, whichever meeting left it.
function minMeetingRooms(intervals) { const starts = intervals.map((meeting) => meeting[0]).sort((a, b) => a - b); const ends = intervals.map((meeting) => meeting[1]).sort((a, b) => a - b); let rooms = 0; let ended = 0; for (let i = 0; i < starts.length; i++) { if (starts[i] < ends[ended]) rooms++; else ended++; } return rooms;}The trap
Sorting by start and comparing each meeting with the one before it counts clashes, not rooms. A meeting can overlap the one before it while an earlier meeting has already finished and left its room free. A chain of meetings where each overlaps only the next one needs two rooms, and this counts one for every link in the chain.
function minMeetingRooms(intervals) { if (!intervals.length) return 0; const sorted = [...intervals].sort((a, b) => a[0] - b[0]); let rooms = 1; for (let i = 1; i < sorted.length; i++) { if (sorted[i][0] < sorted[i - 1][1]) rooms++; // only checks the meeting just before } return rooms;}