Meeting Rooms II
How many rooms do you need? Sort meetings by start time. Use a min-heap of end times representing rooms. For each meeting: if its start ≥ heap top (a room is free), reuse that room. Otherwise, add a new room.
How It Works
Meeting Rooms II asks for the minimum number of rooms to host all meetings. Sort meetings by start time and keep a min-heap of end times, one entry per occupied room. For each meeting, peek at the earliest-ending room: if that meeting has finished (heap top <= current start), pop it and reuse the room; then push the current meeting's end. The heap's maximum size over the sweep is the answer, which equals the peak number of simultaneously running meetings.
Each meeting does O(log n) heap work after an O(n log n) sort. An equivalent sweep-line approach sorts starts and ends separately (or builds +1/-1 events) and tracks the running count — same complexity, and often simpler when only the peak count is needed rather than room assignments.
Step-by-Step Visualization
Code
static int minMeetingRooms(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
PriorityQueue<Integer> endTimes = new PriorityQueue<>();
for (int[] iv : intervals) {
if (!endTimes.isEmpty() && endTimes.peek() <= iv[0]) {
endTimes.poll(); // Reuse room
}
endTimes.add(iv[1]);
}
return endTimes.size();
}Tips & Gotchas
Practice Problems
- 1Meeting Rooms II
- 2Car Pooling
- 3Minimum Number of Platforms
- 4My Calendar II
- 5Divide Intervals Into Minimum Number of Groups
About the Interval Scheduling Pattern
Choose the maximum number of non-overlapping intervals, or schedule activities with minimum resources. The key insight: sorting by end time lets you make optimal local choices that are globally correct.
Greedy is NOT 'try the obvious thing'. It works only when local optimality guarantees global optimality. Sort first (by end time, deadline, ratio), then pick greedily. If greedy fails, try DP.
Common Greedy Interview Problems
- Jump Game
- Activity Selection
- Meeting Rooms II
- Gas Station
- Candy
- Task Scheduler
- Partition Labels
Frequently Asked Questions
Why does the answer equal the peak number of concurrent meetings?
Rooms are interchangeable, so you need at least as many rooms as meetings running at the busiest instant, and the greedy reuse policy shows that many rooms always suffice. Both the heap and the sweep line are just efficient ways to measure that peak.
Heap or sweep line — which should I reach for?
The sweep line (sorted +1/-1 events) is shorter and ideal when you only need the count. The heap keeps identities of rooms alive, so prefer it when you must output an actual room assignment for each meeting or handle rolling capacity like Car Pooling with stops.
Why do I only compare against the heap top instead of scanning all rooms?
The heap top is the room that frees up soonest; if even that room is still busy, every other room is too, so a new room is unavoidable. This single comparison per meeting is what keeps the algorithm at O(n log n).