Solution: Meeting Rooms III

Statement

Given an integer, rooms, which represents the total number of rooms, where each room is numbered from 0 to rooms - 1. Additionally, you are given a $2D$ integer array called meetings, where each element meetings[i] = $[start_i, end_i]$ indicates that a meeting will be held in the half-closed interval $[start_i, end_i)$. Each $start_i$​ is unique.

Meetings are allocated to rooms in the following manner:

1. Each meeting will take place in the unused room with the lowest number.

2. If there are no available rooms, the meeting will be delayed until a room becomes free. The delayed meeting should have the same duration as the original meeting.

3. When a room is vacated, the meeting with the earliest original start time is given priority for that room.

Your task is to determine the room number that hosted the most meetings. If there are multiple rooms, return the room with the lowest number.

Note: A half-closed interval [a, b) is the interval between a and b, including a and not including b.

Constraints:

• $1 \leq$ rooms $\leq 100$

• $1 \leq$ meetings.length $\leq 1000$

• meetings[i].length == $2$

• $0 \leq start_i < end_i \leq 10000$

Solution

We use a two-heap approach for optimal scheduling to determine which room hosts the most meetings. One min heap keeps track of available rooms, ordered by room number, while the other tracks rooms currently in use, ordered by their next availability (i.e., meeting end time). This setup ensures we always have quick access to the room that becomes free the earliest or the lowest-numbered available room.

As all meeting start times are unique, we sort the meetings by their start time to process them chronologically. For each meeting:

• Freeing up rooms: Before scheduling the current meeting, we remove entries from the in-use heap whose end times are less than or equal to the current meeting’s start time. Each freed room is pushed back into the available heap.

• Assigning a room:

  • If the available heap is not empty, we pop the room with the lowest number and assign the meeting to it.

  • If no room is available, we pop the room from the in-use heap with the earliest end time. We delay the meeting to start at the room’s available time, then reassign it back into the in-use heap with the new end time.

• Tracking usage: Each time a room is assigned, we increment its usage counter.

After processing all meetings, we scan the counters and return the room with the highest count. The room with the lowest number is selected in case of a tie.

The steps of the algorithm are as follows:

1. Initialize a count array of size equal to the number of rooms to track the number of meetings held by each room.

2. Create two min heaps:

   1. available: Contains free room numbers.

   2. usedRooms: Contains pairs of (end time, room number) for rooms currently in use.

3. Populate the available min heap with all room numbers [0, 1, 2, ..., rooms-1].

4. Sort the meetings list by their startTime to process them in chronological order.

5. For each meeting interval (startTime, endTime):

   1. Free up rooms: While the top room in usedRooms has an endTime ≤ startTime, remove it from usedRooms and add the room back to available.

   2. If no rooms are available, pop the room that will be free soonest from usedRooms. As the meeting must be delayed, calculate its new endTime by extending the duration starting from the previous room’s endTime.

   3. Allocate the smallest available room (pop from available) and push its new (endTime, room) into usedRooms.

   4. Increment that room’s meeting count in the count array.

6. After all meetings are processed, return the room’s index with the maximum meeting count. In case of a tie, return the smallest index.

Let’s look at the following illustration to get a better understanding of the solution: