Meeting Rooms II
Problem Statement
Given an array of meeting time intervals, return the minimum number of conference rooms required so every meeting can be held without overlap.
Input
An integer matrix intervals, where intervals[i] = [starti, endi] represents one meeting.
Output
An integer: the minimum number of rooms needed to host all meetings.
Constraints
- •
0 <= intervals.length <= 10^4 - •
0 <= starti < endi <= 10^6
Examples
Example 1
intervals = [[0,30],[5,10],[15,20]]
2Example 2
intervals = [[7,10],[2,4]]
1Learning Objectives
- Recognise room allocation as a maximum-overlap scheduling problem.
- Use a min-heap of end times to find the room that becomes free earliest.
- Explain why sorting by start time makes room requests chronological.
- Compare the heap solution with the sorted starts and ends sweep.
Intuition
Pattern Recognition
The signal is minimum number of rooms, which means we need the maximum number of meetings active at the same time. The trap is checking only the last meeting assigned to a room, because the reusable room is the one that ends earliest, not necessarily the most recently seen one.
Sort meetings by start time so they request rooms in chronological order. A min-heap of end times keeps the earliest available room at the top. If that earliest end is still after the current start, every allocated room is busy and a new room is required. If it is at or before the current start, reuse that room by replacing its end time.
Common mistakes
- ×Using a max-heap and hiding the room that frees first.
- ×Forgetting that **end <= start** allows room reuse.
- ×Returning the number of intervals instead of the maximum simultaneous overlap.
- ×Sorting by end time for the heap solution, which loses the order in which meetings request rooms.
Algorithm Explanation
Key idea
Sort meetings by start time. Store one end time per allocated room in a min-heap. The heap root is the room that becomes free first. For each meeting, reuse that room when earliest end <= current start; otherwise allocate a new room. The largest heap size seen is the minimum number of rooms.
Interval walkthrough
Use intervals = [[0,30],[5,10],[15,20]]. On the number line, [0,30] occupies room 1, so the heap is [30]. Meeting [5,10] starts while 30 is still active, so allocate room 2 and the heap becomes [10,30]. Meeting [15,20] sees earliest end 10, which lies before 15. Poll 10, reuse that room, and push 20, leaving [20,30]. The heap never grows beyond 2.
Algorithm
- Return 0 for an empty interval list.
- Sort intervals by increasing start time.
- Create a min-heap of room end times.
- For each meeting, compare its start with the smallest end time in the heap.
- If the smallest end time is less than or equal to the current start, poll it because that room is free.
- Push the current meeting end time.
- Track and return the maximum heap size seen during the scan.
Solutions
Solution 1: Min-heap of room end times
Use this as the standard interview solution because it directly models rooms becoming available over time.
After sorting by start time, keep a min-heap of room end times. The root is the only room that matters for reuse: if the earliest-ending room is still busy, every allocated room is busy.
Step-by-step
- Handle an empty input by returning 0.
- Sort meetings by start time.
- Maintain a min-heap containing the end time of each allocated room.
- Before placing the current meeting, poll the root if it ends at or before the current start.
- Push the current end time because the meeting now occupies a room.
- Update the answer with the heap size after the push.
O(n log n)
O(n)
Sorting and heap operations dominate the runtime. The heap can hold one end time for every room in the worst case.
Java implementation
Solution 2: Separate sorted starts and ends sweep
Use this when you want the cleanest maximum-overlap view and do not need to model individual rooms.
Sort all start times and all end times independently. Sweep starts from left to right while advancing the end pointer past meetings that have already finished. The number of active meetings after each start is the number of rooms currently needed.
Step-by-step
- Copy all starts into starts and all ends into ends.
- Sort both arrays.
- Keep endIndex at the earliest meeting end not yet released.
- Before counting a new start, advance endIndex while ends[endIndex] <= current start because those rooms are free.
- Count the current meeting as active and update the maximum active count.
- Return the maximum active count as the room requirement.
O(n log n)
O(n)
The two arrays take O(n) space. Sorting dominates; the sweep itself is linear.
Java implementation
Dry Run
Sample input
intervals = [[0,30],[5,10],[15,20]]. Heap values are room end times, shown in sorted order for readability.
| meeting | heap before | reuse check | heap after | rooms needed |
|---|---|---|---|---|
| [0,30] | [] | no room exists | [30] | 1 |
| [5,10] | [30] | 30 > 5, allocate a new room | [10,30] | 2 |
| [15,20] | [10,30] | 10 <= 15, reuse the earliest room | [20,30] | 2 |
The heap reaches size 2 and never needs a third room. The root comparison captures the only room that can possibly be reused first.
Interview Tips
Say that the heap stores end times, not full intervals. That makes the comparator and reuse check obvious. Then connect the answer to maximum overlap: each time the heap grows, another room is simultaneously needed. If asked for an alternative, present the sorted starts and ends sweep as the same overlap count without explicit room objects.
Likely follow-ups
- How would you return the actual room assignment for each meeting?
- How would the solution change if meetings arrived online and could not be sorted first?
- Can you solve the boolean Meeting Rooms problem as a simpler version?
- How would you support cancellations after rooms have been assigned?
Similar Problems
Key Takeaways
- The answer is the maximum number of overlapping meetings.
- A min-heap exposes the room that frees earliest.
- If the earliest room is still busy, all allocated rooms are busy.
- Separate sorted starts and ends provide a second optimal overlap-counting view.