Meeting Rooms II
Problem
Given an array of meeting time intervals consisting of start and end times, return the minimum number of conference rooms required to hold all the meetings without overlaps.
- 1 ≤ intervals.length ≤ 10⁴
- 0 ≤ start_i < end_i ≤ 10⁶
Example
intervals = [[0,30],[5,10],[15,20]]2The algorithm first sorts the intervals by start time: [[0,30],[5,10],[15,20]]. It initializes a min-heap to track end times of ongoing meetings. The first meeting [0,30] is added to the heap. The second meeting [5,10] starts before the earliest ending meeting (30), so it requires a new room; its end time 10 is pushed onto the heap. The third meeting [15,20] starts after the earliest ending meeting (10), so the room that ended at 10 is freed (popped from the heap), and the new meeting's end time 20 is pushed. The heap size never exceeds 2, so 2 rooms are needed.
Approach
Straightforward Solution
A brute-force approach checks every pair of intervals for overlap, counting maximum overlaps, resulting in O(n^2) time complexity, which is too slow for large inputs.
Core Observation
The minimum number of rooms required equals the maximum number of overlapping meetings at any point in time. Sorting intervals by start time allows sequential processing, and a min-heap efficiently tracks the earliest finishing meeting to free rooms.
Path to Optimal
PreviewSorting intervals by start time orders meetings chronologically. Using a min-heap to track end times of ongoing meetings allows efficient detection of room availability: if the current meeting starts after or at the earliest end time, that room can be reused (pop from heap)…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewSort intervals by start time. Iterate through each meeting, and while the min-heap is not empty and the current meeting's start time is greater than or equal to the earliest end time in the heap, pop from the heap to free a room…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(n log n)
Sorting the intervals takes O(n log n). Each interval is pushed and popped at most once from the min-heap, each operation costing O(log n), resulting in O(n log n) overall.
Space
O(n)
The min-heap can hold up to n end times in the worst case (all meetings overlap), so auxiliary space is O(n). This space is necessary to track ongoing meetings.
Pattern Spotlight
Heap / Priority Queue (Interval Scheduling Resource Allocation)
Use a min-heap to track the earliest finishing meeting to efficiently free rooms; the heap size at any time reflects the number of concurrent meetings, which equals the minimum rooms needed.
Solution
| 1 | import heapq
|
| 2 |
|
| 3 | class Solution:
|
| 4 | def minMeetingRooms(self, intervals: list[list[int]]) -> int:
|
| 5 | intervals.sort(key=lambda i: i[0])
|
| 6 |
|
| 7 | min_heap = []
|
| 8 | max_rooms = 0
|
| 9 |
|
| 10 | for start, end in intervals:
|
| 11 | while min_heap and start >= min_heap[0]:
|
| 12 | heapq.heappop(min_heap)
|
| 13 |
|
| 14 | heapq.heappush(min_heap, end)
|
| 15 | max_rooms = max(max_rooms, len(min_heap))
|
| 16 |
|
| 17 | return max_rooms |
Step-by-Step Solution
Sort Meetings by Start Time to Process Chronologically
| 5 | intervals.sort(key=lambda i: i[0])
|
Objective
To order the meetings so that they can be processed in chronological order of their start times.
Key Insight
Sorting intervals by start time is essential because it allows the algorithm to consider meetings in the order they begin, which is necessary to detect overlaps and manage room allocation efficiently. Without sorting, the algorithm cannot reliably track which rooms become free when.
Interview Quick-Check
Core Logic
Sorting by start time ensures that meetings are processed in the order they occur, enabling correct overlap detection.
Common Pitfalls & Bugs
Failing to sort intervals leads to incorrect room allocation because meetings may be processed out of chronological order.
Use Min-Heap to Track Earliest Meeting End Times and Free Rooms
To maintain the end times of ongoing meetings and efficiently determine when rooms become available.
Track Maximum Concurrent Meetings to Determine Minimum Rooms
To record the maximum number of rooms occupied simultaneously during the iteration.
Return the Minimum Number of Rooms Required
To output the final computed minimum number of rooms needed to schedule all meetings.
3 more steps with full analysis available on Pro.
Line Analysis
This solution has 2 Critical lines interviewers watch for.
while min_heap and start >= min_heap[0]:While there are meetings that have ended before the current meeting starts, free those rooms.
Removing all meetings that ended before the current start time frees rooms for reuse, preventing unnecessary room allocation.
heapq.heappop(min_heap)Pop the earliest ending meeting from the min-heap to free a room.
Popping the earliest end time removes the meeting that has finished, making its room available for the current meeting.
Full line-by-line criticality + rationale for all 9 lines available on Pro.
Test Your Understanding
Why does the size of the min-heap at any point represent the minimum number of rooms required?
See the answer with Pro.
Related Problems
Heap / Priority Queue pattern
Don't just read it. Drill it.
Reconstruct Meeting Rooms II from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Meeting Rooms II drill