Meeting Rooms III
Understanding the Problem
We have n rooms and a list of meetings, each with a start and end time. We need to simulate a scheduling process: meetings are processed in order of their start time, each gets assigned to the lowest-numbered available room, and if no room is free, the meeting waits for the earliest room to open up.
The part that needs care is the delay rule. When a meeting can't start on time, it waits until a room frees up, but it keeps its original duration. A meeting originally scheduled for [2, 7] (duration 5) that gets delayed to start at time 10 would end at time 15.
After all meetings are scheduled, we report which room hosted the most meetings. If there's a tie, return the smallest room number.
The work, then, is to track which rooms are free and which are busy, and to quickly find the next room that becomes available.
Key Constraints:
1 <= n <= 100-- The number of rooms is small. Even O(n) scans per meeting are cheap.1 <= meetings.length <= 10^5-- We could have up to 100,000 meetings. This is the dimension that matters for time complexity.0 <= starti < endi <= 5 * 10^5-- Time values can be large, but we don't need to iterate over every time unit. Be careful with integer overflow when meetings are delayed repeatedly.
Approach 1: Brute Force Simulation
Intuition
Maintain an array tracking when each room becomes free. For each meeting, processed in start-time order, scan all rooms to find the best assignment.
If at least one room is free (its end time <= meeting's start time), pick the free room with the lowest index. If no room is free, find the room that becomes free earliest (lowest end time, breaking ties by room index), delay the meeting to start when that room opens, and adjust the end time accordingly.
Algorithm
- Sort meetings by start time.
- Create an array
roomEndTimeof size n, initialized to 0 (all rooms start free). - Create an array
countof size n to track how many meetings each room hosts. - For each meeting
[start, end]: - Scan all rooms. Find the room with the earliest end time. If that end time <= start, it's a free room. Among all free rooms, pick the one with the lowest index.
- If no room is free, pick the room with the smallest end time (lowest index to break ties). The meeting starts at that room's end time, and the new end time is
roomEndTime[room] + (end - start). - Update
roomEndTime[room]and incrementcount[room]. - Return the room index with the highest count (lowest index to break ties).
Visualization and Code
Loading animation...
- Time Complexity: O(m * n) where m is the number of meetings and n is the number of rooms. We sort meetings in O(m log m), then for each meeting we scan all n rooms.
- Space Complexity: O(n). Two arrays of size n for end times and counts.
For each meeting, we scan all n rooms to find the best one. Since n is at most 100, this is fast enough to pass. To remove the per-meeting scan, the next approach replaces the linear search with two heaps that surface the room we need in O(log n).
Approach 2: Sorting + Two Min-Heaps
Intuition
Split the rooms into two groups: available rooms and busy rooms, each in its own min-heap. The available heap is ordered by room number, so its top is always the lowest-numbered free room. The busy heap is ordered by (end time, room number), so its top is always the room that frees up first.
For each meeting, first move rooms from the busy heap back to the available heap if their end time has passed. Then assign the meeting to the lowest-numbered free room, or, if none is free, delay it onto the earliest-ending busy room.
Rule 3 says that when a room frees up, the waiting meeting with the earlier original start time gets it. Processing meetings in sorted start-time order satisfies this without extra bookkeeping: a meeting is only ever assigned after every meeting with an earlier start has already been placed, so the room it receives was never owed to an earlier meeting. The two heaps hold all n rooms between them at every step, so a room is either free or busy, never lost or double-counted.
Algorithm
- Sort meetings by start time.
- Initialize an available min-heap with rooms 0 through n-1 (sorted by room number).
- Initialize an empty busy min-heap (sorted by end time, then room number).
- Create a count array of size n.
- For each meeting
[start, end]: - Move all rooms from the busy heap where
endTime <= startback to the available heap. - If the available heap is non-empty, pop the smallest room number and assign the meeting there.
- If the available heap is empty, pop the room with the earliest end time from the busy heap. The meeting starts at that end time: new end =
poppedEndTime + (end - start). - Push the assigned room with its new end time onto the busy heap. Increment
count[assignedRoom]. - Return the room with the highest count (lowest index for ties).
Visualization and Code
Loading animation...
- Time Complexity: O(m log m + m log n) where m is the number of meetings and n is the number of rooms. Sorting takes O(m log m). Each meeting does O(log n) heap operations. The total room transitions across all meetings is exactly m, so aggregate heap work is O(m log n).
- Space Complexity: O(n). Both heaps together hold exactly n rooms at all times. The count array is also O(n).
The two-heap version is the standard solution: it drops the per-meeting scan to O(log n) while keeping the same sorted-by-start-time simulation that makes the assignment rules correct.