Solution: Meeting Rooms III

Statement

You have an integer, rooms, representing room numbers 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, maintaining 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 highest number of 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 have to determine the room number that holds the most number of meetings. This problem can be solved optimally by using the two-heaps pattern. We will have efficient access to the rooms that get free the earliest by maintaining two min-heaps: one for the available rooms and one for the rooms currently in use. Maintaining these heaps involves keeping the heaps up-to-date as meetings start and end, ensuring that the room with the earliest availability is always at the root of the heaps.

As we know that the start times are unique, meaning no two meetings would start at the same time, we will sort the given meeting intervals based on their start times because this ensures that we process the meetings in chronological order. This way, we can efficiently allocate rooms as they become available. We then schedule the meetings if the rooms are available by checking the available rooms heap. If no room is available, we wait until a room becomes free by checking the used rooms heap. We keep doing this for all the meetings and keep a count of meetings for each room. Once all meetings are scheduled, we return the room number with the most meetings held.

Let’s go through the algorithm to see how we will reach the solution:

1. Initialize an integer array counter to keep track of the number of meetings held in each room. The size of the array is the number of given rooms.

2. We will have two min-heaps; available and usedRooms. The available heap represents the available rooms sorted by the room numbers, and the usedRooms heap contains the rooms in use along with the time they become free again.

3. After sorting the given meeting intervals, we go through all the meetings and do the following:

   1. Free up rooms that have completed their meetings until the current meeting starts. Move these rooms from usedRooms to available by popping them from usedRooms and pushing them to available.

   2. Next comes the scheduling of the meetings. We check if any rooms are available by looking at the available heap. If no room is available, we retrieve the meeting with the smallest ending time from usedRooms . This is the room that will be free as soon as possible. Hence, we will delay the current meeting until the meeting scheduled in this room ends.

   3. Once the room is available, we will schedule the meeting by pushing the updated endTime and the room number to usedRooms. Increment the count for the allocated room in the counter array.

4. After processing all meetings, we return the room with the highest count of meetings from the counter array. In case of a tie, we return the room with the smallest number.

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