Meeting Rooms II
The key idea
Sort meetings by start time, then keep a min-heap of the end times of meetings currently using a room. For each new meeting, if the earliest-ending room is already free (its end <= this start) reuse it; otherwise open a new room. The heap size is the number of rooms in use, and its peak is the answer.
Problem
Given an array of meeting time intervals intervals where intervals[i] = [start_i, end_i], return the minimum number of conference rooms required so that no two overlapping meetings share a room.
Two meetings overlap when one starts before the other ends. A meeting that starts exactly when another ends does not overlap, so they may reuse the same room.
Constraints
1 <= intervals.length <= 10^40 <= start_i < end_i <= 10^6
Examples
Input: intervals = [[0,30],[5,10],[15,20]]
Output: 2
Input: intervals = [[7,10],[2,4]]
Output: 1
Complexity
Time: O(n log n) Space: O(n)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Heap / Priority Queue problems
- Find K Pairs with Smallest SumsMEDIUM
- Find Median from Data StreamHARD
- IPOHARD
- K Closest Points to OriginMEDIUM
- Kth Largest Element in a StreamEASY
- Kth Largest Element in an ArrayMEDIUM
- Last Stone WeightEASY
- Maximum Subsequence ScoreMEDIUM
- Meeting Rooms IIIHARD
- Merge k Sorted ListsHARD
- Minimum Interval to Include Each QueryHARD
- Single-Threaded CPUMEDIUM