Meeting Rooms III
The key idea
Process meetings in start-time order. Always give a waiting meeting the room that frees up earliest; break a tie in free-time by the lowest room number. A min-heap of busy rooms keyed by
(free_time, room) makes both choices one pop.Problem
You are given an integer n. There are n rooms numbered from 0 to n - 1. You are also given a 2D integer array meetings where meetings[i] = [start_i, end_i] means a meeting is held during the half-closed interval [start_i, end_i).
Meetings are assigned to rooms by these rules. Each meeting takes place in the unused room with the lowest number. If no room is free, the meeting is delayed until a room frees up, keeping its same duration. When a room frees up, the delayed meeting with the earliest original start time is given that room.
Return the number of the room that held the most meetings. If there is a tie, return the room with the lowest number.
Constraints
1 <= n <= 1001 <= meetings.length <= 10^5meetings[i].length == 20 <= start_i < end_i <= 5 * 10^5- All the values of
start_iare unique.
Examples
Input: n = 2, meetings = [[0,10],[1,5],[2,7],[3,4]]
Output: 0
Input: n = 3, meetings = [[1,20],[2,10],[3,5],[4,9],[6,8]]
Output: 1
Complexity
Time: O(m log m + m 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 IIMEDIUM
- Merge k Sorted ListsHARD
- Minimum Interval to Include Each QueryHARD
- Single-Threaded CPUMEDIUM