Meeting Rooms II
Problem Statement
You are given an array intervals where intervals[i] = [start_i, end_i] represents one meeting. Return the minimum number of conference rooms required so every meeting can be held.
If a meeting ends at time t, another meeting starting at time t may reuse the same room.
Input
An array intervals of meeting time ranges.
Output
An integer: the minimum number of rooms needed to schedule all meetings without room conflicts.
Constraints
- •
0 <= intervals.length <= 10^4 - •
intervals[i].length == 2 - •
0 <= start_i < end_i <= 10^6
Examples
Example 1
intervals = [[0,30],[5,10],[15,20]]
2Example 2
intervals = [[7,10],[2,4]]
1Example 3
intervals = [[1,5],[5,8],[6,9]]
2Learning Objectives
- Use a min-heap to track the earliest room that becomes available.
- Explain why the maximum number of simultaneous meetings equals the minimum room count.
- Recognise the equivalent sweep-line formulation using sorted starts and ends.
- Handle the reuse boundary where **end <= start** means the room is free.
Intuition
Greedy Insight: Process meetings by increasing start time. When a new meeting begins, the only room that matters first is the one that ends earliest. If even that room is still occupied, every other occupied room ends no earlier, so a new room is unavoidable.
The min-heap stores room end times, with the earliest-finishing room at the top. Reusing that room is safe because it frees the most constrained resource first. If it cannot be reused, no currently allocated room can be reused for this meeting.
The wrong sort key trap is to sort by end time and assign rooms from there, or to keep the latest-ending room at the top. Scheduling decisions are triggered by starts, but resource reuse is determined by the earliest end. This start-time scan plus earliest-end heap is the greedy pairing that makes the solution work.
Common mistakes
- ×Using a max-heap of end times, which hides the room most likely to be reusable.
- ×Treating **end == start** as a conflict and allocating an unnecessary room.
- ×Returning the number of currently active meetings after a sweep without tracking the maximum.
- ×Sorting by end time first, which processes meetings before their room demand actually occurs.
Algorithm Explanation
Greedy strategy Sort meetings by start time. Maintain a min-heap of room end times. For each meeting, reuse the earliest-ending room if it has already ended; otherwise allocate a new room.
Why it works At the current start time, the heap top is the room that becomes free first. If that end time is greater than the current start, then all other room end times are also greater, so every existing room is occupied and a new room is necessary. If the top is at most the current start, reusing it preserves the room count and keeps the allocation feasible.
Proof of correctness Consider any step where the greedy algorithm processes the next meeting in start-time order. If the earliest room end is after this meeting starts, no schedule using the already allocated rooms can place this meeting in one of them, because every room ends no earlier than the heap top. Adding a room is therefore forced in every optimal schedule.
If the earliest room end is at or before the current start, greedy reuses that room. Take an optimal schedule that reuses some available room for this meeting. If it is not the earliest-ending room, swap the current meeting into the earliest-ending room instead. That room was already free, and the room originally used remains free as well, so no later meeting loses feasibility and the number of rooms does not increase. Repeating this exchange makes the optimal schedule match the greedy choices.
Algorithm
- Sort intervals by start time.
- Create a min-heap containing end times of allocated rooms.
- For each meeting, if the smallest end time is <= start, remove it because that room can be reused.
- Add the current meeting end time to the heap.
- The heap size after all meetings is the number of rooms allocated.
Solutions
Solution 1: Min-heap of room end times
The heap represents allocated rooms by their next available time. For each chronological meeting, the earliest available room either can host it or proves that no existing room can.
Step-by-step
- Sort meetings by start time.
- For each meeting, check the smallest end time in the heap.
- If that end time is <= currentStart, poll it and reuse that room.
- Push the current end time because the chosen room is now occupied until that end.
- Return the heap size, which is the total number of rooms that had to be allocated.
O(n log n)
O(n)
Sorting costs O(n log n), and each meeting performs at most one heap insertion and one heap removal.
Java implementation
Solution 2: Chronological sweep with starts and ends
Use this version when you want to emphasise that the answer is the peak number of active meetings. It avoids a heap by sorting start times and end times separately.
Separate all starts and ends, then sweep starts from earliest to latest. Before counting a new meeting, release every room whose end time is at most that start. The maximum active count seen during the sweep is the room requirement.
Step-by-step
- Copy starts into one array and ends into another.
- Sort both arrays.
- For each start time, advance the end pointer while meetings have ended.
- Add the current meeting to the active room count and update the maximum.
- Return the maximum active count.
O(n log n)
O(n)
Two arrays are sorted, then swept linearly.
Java implementation
Dry Run
Sample input
intervals = [[0,30],[5,10],[15,20]]. Sort by start time and track the min-heap of room end times.
| meeting | heap before | action | heap after | rooms so far |
|---|---|---|---|---|
| [0,30] | [] | allocate a new room | [30] | 1 |
| [5,10] | [30] | 30 > 5, allocate a new room | [10,30] | 2 |
| [15,20] | [10,30] | 10 <= 15, reuse that room | [20,30] | 2 |
The heap size never exceeds 2, and the final heap also contains two room end times. Therefore two rooms are necessary and sufficient.
Interview Tips
State the lower bound first: if k meetings overlap at one instant, at least k rooms are required. Then show the greedy heap achieves exactly that by reusing the earliest-ending room whenever possible. If the interviewer prefers sweep line, pivot to sorted starts and ends; it is the same active-count idea without explicitly naming rooms.
Likely follow-ups
- How would you return the actual room assignment for each meeting?
- How would you handle a required cleanup buffer between meetings?
- How would the solution change if meetings arrived online and could not be sorted first?
- Can you solve it with sorted start and end arrays instead of a heap?
Similar Problems
Key Takeaways
- Minimum rooms equals the maximum number of simultaneous meetings.
- Process meetings by start time, but choose rooms by earliest end time.
- A min-heap answers whether any allocated room can be reused now.
- Sorted starts and ends provide an equivalent sweep-line solution.