# 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]`

= **half-closed** interval

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 betweenaandbincludingaandnot includingb.

**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:

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`

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.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`

to`available`

by popping them from`usedRooms`

and pushing them to`available`

.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.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.

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 soluti

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.