Solution: Meeting Rooms III
Let's solve the Meeting Rooms III problem using the Two Heaps pattern.
We'll cover the following
Statement
You have an integer, rooms
, representing room numbers from 0
to rooms−1
. Additionally, you are given a meetings
, where each element meetings[i]
=
Meetings are allocated to rooms in the following manner:
Each meeting will take place in the unused room with the lowest number.
If there are no available rooms, the meeting will be delayed until a room becomes free, maintaining the same duration as the original meeting.
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:
rooms
meetings.length
meetings[i].length
==
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:
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.We will have two min-heaps;
available
andusedRooms
. Theavailable
heap represents the available rooms sorted by the room numbers, and theusedRooms
heap contains the rooms in use along with the time they become free again.After sorting the given meeting intervals, we go through all the meetings and do the following:
Free up rooms that have completed their meetings until the current meeting starts. Move these rooms from
usedRooms
toavailable
by popping them fromusedRooms
and pushing them toavailable
.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 fromusedRooms
. 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.Once the room is available, we will schedule the meeting by pushing the updated
endTime
and the room number tousedRooms
. Increment the count for the allocated room in thecounter
array.
After processing all
meetings
, we return the room with the highest count of meetings from thecounter
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 soluti
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.