Watch 10 video solutions for Meeting Rooms III, a hard level problem involving Array, Hash Table, Sorting. This walkthrough by NeetCodeIO has 35,386 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an integer n. There are n rooms numbered from 0 to n - 1.
You are given a 2D integer array meetings where meetings[i] = [starti, endi] means that a meeting will be held during the half-closed time interval [starti, endi). All the values of starti are unique.
Meetings are allocated to rooms in the following manner:
Return the number of the room that held the most meetings. If there are multiple rooms, return the room with the lowest number.
A half-closed interval [a, b) is the interval between a and b including a and not including b.
Example 1:
Input: n = 2, meetings = [[0,10],[1,5],[2,7],[3,4]] Output: 0 Explanation: - At time 0, both rooms are not being used. The first meeting starts in room 0. - At time 1, only room 1 is not being used. The second meeting starts in room 1. - At time 2, both rooms are being used. The third meeting is delayed. - At time 3, both rooms are being used. The fourth meeting is delayed. - At time 5, the meeting in room 1 finishes. The third meeting starts in room 1 for the time period [5,10). - At time 10, the meetings in both rooms finish. The fourth meeting starts in room 0 for the time period [10,11). Both rooms 0 and 1 held 2 meetings, so we return 0.
Example 2:
Input: n = 3, meetings = [[1,20],[2,10],[3,5],[4,9],[6,8]] Output: 1 Explanation: - At time 1, all three rooms are not being used. The first meeting starts in room 0. - At time 2, rooms 1 and 2 are not being used. The second meeting starts in room 1. - At time 3, only room 2 is not being used. The third meeting starts in room 2. - At time 4, all three rooms are being used. The fourth meeting is delayed. - At time 5, the meeting in room 2 finishes. The fourth meeting starts in room 2 for the time period [5,10). - At time 6, all three rooms are being used. The fifth meeting is delayed. - At time 10, the meetings in rooms 1 and 2 finish. The fifth meeting starts in room 1 for the time period [10,12). Room 0 held 1 meeting while rooms 1 and 2 each held 2 meetings, so we return 1.
Constraints:
1 <= n <= 1001 <= meetings.length <= 105meetings[i].length == 20 <= starti < endi <= 5 * 105starti are unique.Problem Overview: You are given n meeting rooms and a list of meeting time intervals. Each meeting must be assigned to the lowest indexed available room. If no room is free, the meeting waits until the earliest room becomes available. After scheduling all meetings, return the room that handled the most meetings.
Approach 1: Priority Queue with Room Availability Tracking (O(m log n) time, O(n) space)
This is the standard optimal approach. First sort meetings by start time using sorting. Maintain two min-heaps: one heap for available rooms (ordered by room index) and another for occupied rooms storing (endTime, roomId). As you iterate through meetings, release rooms whose end time is less than or equal to the current start time. If a room is available, assign the meeting immediately. If not, pop the earliest finishing room and delay the meeting until that time. Track how many meetings each room handles and return the index with the maximum count. Heap operations keep scheduling efficient.
Approach 2: Using Priority Queue for Room Scheduling (O(m log n) time, O(n) space)
This variation focuses on modeling the scheduling process directly. Maintain a min-heap of busy rooms keyed by meeting end time and another heap of free room indices. When processing a meeting, repeatedly pop from the busy heap until rooms become free. If no room is free, extend the meeting start to the earliest end time and reuse that room. This is effectively a scheduling simulation powered by a heap (priority queue). The approach is common in interview discussions because it cleanly separates room selection and meeting completion events.
Approach 3: Simulation with Event Queue (O(m log n) time, O(n) space)
Another perspective treats the problem as a full simulation. Meetings create "start events" and room releases create "end events". A priority queue processes events in chronological order. When a meeting begins, allocate the smallest available room. If none are available, reschedule the meeting when the next room frees up. This approach mirrors real-world scheduling systems and helps when implementing the logic in languages like C++ with explicit event handling.
Approach 4: Sorting and Greedy Allocation (O(m log n) time, O(n) space)
A greedy strategy works after sorting meetings by start time. Always assign the earliest available room with the smallest index. If all rooms are busy, greedily select the meeting that finishes first and extend its timeline. Internally this still relies on a heap to efficiently track the earliest finishing meeting, but the reasoning focuses on greedy scheduling rather than explicit simulation. Concepts from array processing and interval scheduling drive the logic.
Recommended for interviews: The priority queue with room availability tracking is what most interviewers expect. It demonstrates understanding of interval scheduling, heaps, and simulation. Starting with a basic simulation shows you understand the constraints, but implementing the two-heap optimal approach proves you can design scalable scheduling systems.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Priority Queue with Room Availability Tracking | O(m log n) | O(n) | Best general solution for interviews and production scheduling problems |
| Priority Queue Room Scheduling | O(m log n) | O(n) | When modeling busy and free rooms separately for clarity |
| Simulation with Event Queue | O(m log n) | O(n) | Useful when implementing a full event-driven simulation |
| Sorting and Greedy Allocation | O(m log n) | O(n) | When reasoning about interval scheduling and greedy strategies |