Problem Understanding
Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), find the minimum number of conference rooms required.
Example:
- Input:
[[0,30],[5,10],[15,20]] - Output:
2 - Explanation: Meeting 1 (
0-30) requires a room. Meeting 2 (5-10) overlaps, so it needs a new room. Meeting 3 (15-20) also overlaps with Meeting 1, but it starts after Meeting 2 ends, so it can reuse Meeting 2's room.
Note: LeetCode 253, linked above, is a LeetCode Premium problem — opening it needs a Premium subscription. Everything needed to solve it is on this page.
Algorithm Strategy
The number of rooms needed is the most meetings running at the same moment. Two sorted arrays find it without tracking which meeting is in which room.
- Sort the start times into
startsand, separately, the end times intoends. - Walk the starts with
i, keepingendPtron the earliest end time not yet used. - Compare
starts[i]withends[endPtr]:- If
starts[i] < ends[endPtr], no meeting has finished yet, so every room is busy: open a new room (rooms++). - Otherwise some meeting has already ended: its room is free, so reuse it and move
endPtrto the next end time. The room count does not change.
- If
- Return
rooms.
Only the count of finished meetings matters, not which one finished, which is why the start and end times can be sorted apart.
Alternative: sort the meetings by start and keep a min-heap of the end times of meetings in progress — pop the top when it is <= start, push the new end, and the heap's largest size is the answer. It is also O(N log N).
Interactive Visualization
Watch how we allocate spaces (rooms) based on availability.
Dry Run
Input: [[0,30], [5,10], [15,20]]
starts = [0, 5, 15], ends = [10, 20, 30]
| i | starts[i] |
ends[endPtr] |
Compare | Action | rooms | endPtr |
|---|---|---|---|---|---|---|
| 0 | 0 | 10 | 0 < 10 |
All busy: new room | 1 | 0 |
| 1 | 5 | 10 | 5 < 10 |
All busy: new room | 2 | 0 |
| 2 | 15 | 10 | 15 >= 10 |
A meeting ended: reuse its room | 2 | 1 |
| Final | - | - | - | - | 2 | - |
Edge Cases & Common Mistakes
- Exact Match:
[1,5]and[5,10]. The second meeting starts at 5 and the first ends at 5;5 < 5is false, so the room is reused and one room is enough. - Single Meeting: Needs 1 room.
- All at once: When every meeting starts before any ends, each one opens a room and the answer is
n. - Sorting the pairs together: Sorting
endsmust be separate fromstarts; keeping each end next to its own start gives the wrong count.
Solution
Two pointers over the sorted start and end times, O(N log N).
Meeting Rooms II Code
1var minMeetingRooms = function(intervals) {2 const starts = intervals.map((m) => m[0]).sort((a, b) => a - b);3 const ends = intervals.map((m) => m[1]).sort((a, b) => a - b);45 let rooms = 0;6 let endPtr = 0;7 for (let i = 0; i < starts.length; i++) {8 if (starts[i] < ends[endPtr]) {9 rooms++;10 } else {11 endPtr++;12 }13 }14 return rooms;15};