# Meeting Rooms III
**Difficulty:** HARD
[External](https://leetcode.com/problems/meeting-rooms-iii)
Canonical: https://scaleengineer.com/dsa/problems/meeting-rooms-iii
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table, Heap (Priority Queue)
**Companies:** [PayPal](https://scaleengineer.com/companies/paypal), [Pinterest](https://scaleengineer.com/companies/pinterest)
---
## Problem
You are given an integer `n`. There are `n` rooms numbered from `0` to `n - 1`.

You are given a 2D integer array `meetings` where `meetings[i] = [starti, endi]` means that a meeting will be held during the **half-closed** time interval `[starti, endi)`. All the values of `starti` are **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 becomes unused, meetings that have an earlier original **start** time should be given the room.

Return _the **number** of the room that held the most meetings._ If there are multiple rooms, return _the room with the **lowest** number._

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

**Example 1:**

**Input:** n = 2, meetings = [[0,10],[1,5],[2,7],[3,4]]
**Output:** 0
**Explanation:**
- At time 0, both rooms are not being used. The first meeting starts in room 0.
- At time 1, only room 1 is not being used. The second meeting starts in room 1.
- At time 2, both rooms are being used. The third meeting is delayed.
- At time 3, both rooms are being used. The fourth meeting is delayed.
- At time 5, the meeting in room 1 finishes. The third meeting starts in room 1 for the time period [5,10).
- At time 10, the meetings in both rooms finish. The fourth meeting starts in room 0 for the time period [10,11).
Both rooms 0 and 1 held 2 meetings, so we return 0. 

**Example 2:**

**Input:** n = 3, meetings = [[1,20],[2,10],[3,5],[4,9],[6,8]]
**Output:** 1
**Explanation:**
- At time 1, all three rooms are not being used. The first meeting starts in room 0.
- At time 2, rooms 1 and 2 are not being used. The second meeting starts in room 1.
- At time 3, only room 2 is not being used. The third meeting starts in room 2.
- At time 4, all three rooms are being used. The fourth meeting is delayed.
- At time 5, the meeting in room 2 finishes. The fourth meeting starts in room 2 for the time period [5,10).
- At time 6, all three rooms are being used. The fifth meeting is delayed.
- At time 10, the meetings in rooms 1 and 2 finish. The fifth meeting starts in room 1 for the time period [10,12).
Room 0 held 1 meeting while rooms 1 and 2 each held 2 meetings, so we return 1. 

**Constraints:**

* `1 <= n <= 100`
* `1 <= meetings.length <= 105`
* `meetings[i].length == 2`
* `0 <= starti < endi <= 5 * 105`
* All the values of `starti` are **unique**.

# Approaches
## Naive Simulation with Linear Scans
This approach simulates the meeting allocation process by iterating through meetings sorted by start time. For each meeting, it performs a linear scan through the rooms to find an available one or the one that frees up earliest. This is straightforward but less efficient for a large number of rooms.
**Time:** O(M log M + M * N), where M is the number of meetings and N is the number of rooms. Sorting takes O(M log M). The main loop iterates M times, and inside it, we may perform a linear scan of N rooms, resulting in O(M * N). · **Space:** O(N) to store the availability time and meeting counts for each room.
**Pros:** Simple logic, easy to understand and implement.; Low memory overhead, uses basic arrays.
**Cons:** Inefficient time complexity O(M*N), which can be slow if M and N are large.
### Explanation
In this method, we directly simulate the process described in the problem. We maintain an array, `roomAvailabilityTime`, of size `n`, where each element stores the time when the corresponding room will become free. Another array, `meetingCounts`, of the same size, keeps track of how many meetings each room has hosted.

First, we must sort the `meetings` array by their start times. This ensures we process meetings in chronological order, which is a key requirement for correctly handling priorities for delayed meetings.

We then iterate through each sorted meeting `[start, end]`. For each meeting, we attempt to find an available room. We do this by scanning through our `roomAvailabilityTime` array from index `0` to `n-1`. The first room `i` for which `roomAvailabilityTime[i] <= start` is the one we select, as it satisfies both being available and having the lowest index.

If such a room is found, we schedule the meeting in it. This involves updating `roomAvailabilityTime[i]` to the meeting's `end` time and incrementing `meetingCounts[i]`. 

If, after checking all rooms, none are available at the meeting's `start` time, the meeting must be delayed. It has to wait for the first room to become free. To find this room, we perform another linear scan over `roomAvailabilityTime` to find the room `j` with the minimum availability time. This meeting will start at `roomAvailabilityTime[j]`. The duration of the meeting remains `end - start`. Therefore, the new end time for this meeting in room `j` will be `roomAvailabilityTime[j] + (end - start)`. We update `roomAvailabilityTime[j]` to this new value and increment `meetingCounts[j]`.

After processing all meetings, we iterate through the `meetingCounts` array to find the room index that has the highest count. In case of a tie, the problem specifies to return the room with the lower index, which we can handle during our search for the maximum.

```java
import java.util.Arrays;

class Solution {
    public int mostBooked(int n, int[][] meetings) {
        Arrays.sort(meetings, (a, b) -> Integer.compare(a[0], b[0]));

        long[] roomAvailabilityTime = new long[n];
        int[] meetingCounts = new int[n];

        for (int[] meeting : meetings) {
            int start = meeting[0];
            int end = meeting[1];
            boolean roomFound = false;
            int earliestFreeRoom = 0;
            long earliestFreeTime = Long.MAX_VALUE;

            // Find an available room with the lowest index
            for (int i = 0; i < n; i++) {
                if (roomAvailabilityTime[i] <= start) {
                    roomAvailabilityTime[i] = end;
                    meetingCounts[i]++;
                    roomFound = true;
                    break;
                }
                if (roomAvailabilityTime[i] < earliestFreeTime) {
                    earliestFreeTime = roomAvailabilityTime[i];
                    earliestFreeRoom = i;
                }
            }

            // If no room was available, use the one that becomes free earliest
            if (!roomFound) {
                roomAvailabilityTime[earliestFreeRoom] += (end - start);
                meetingCounts[earliestFreeRoom]++;
            }
        }

        int maxMeetings = -1;
        int resultRoom = -1;
        for (int i = 0; i < n; i++) {
            if (meetingCounts[i] > maxMeetings) {
                maxMeetings = meetingCounts[i];
                resultRoom = i;
            }
        }
        return resultRoom;
    }
}
```
### Algorithm
* Sort the `meetings` array by start time.
* Initialize `roomAvailabilityTime` array of size `n` with zeros to track when each room becomes free.
* Initialize `meetingCounts` array of size `n` with zeros.
* Iterate through each sorted `meeting [start, end]`:
  * Linearly scan rooms `0` to `n-1` to find the first available room `i` (where `roomAvailabilityTime[i] <= start`).
  * If an available room `i` is found, assign the meeting to it. Update `roomAvailabilityTime[i] = end` and increment `meetingCounts[i]`.
  * If no room is available, find the room `j` that will be free the earliest by finding the minimum `roomAvailabilityTime`. Assign the delayed meeting to room `j`. The new end time will be `roomAvailabilityTime[j] + (end - start)`. Update `roomAvailabilityTime[j]` and increment `meetingCounts[j]`.
* After iterating through all meetings, find the room index with the maximum count in `meetingCounts`. Handle ties by choosing the smaller index.

## Optimized Simulation with Min-Heaps
This is a more efficient approach that uses two priority queues (min-heaps) to manage room allocation. One heap tracks available rooms to quickly find the one with the lowest index, and the other tracks occupied rooms to quickly find the one that will free up next. This avoids costly linear scans.
**Time:** 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 of the M meetings involves a constant number of heap operations, which take O(log N) time. Thus, the total time for processing all meetings is O(M log N). · **Space:** O(N) to store the elements in the two heaps and the meeting counts. In the worst case, all N rooms could be in one of the heaps.
**Pros:** Highly efficient time complexity O(M log M + M log N), suitable for the given constraints.; Elegantly models the problem's state transitions using priority queues.
**Cons:** More complex to implement compared to the naive approach due to the use of heaps.; Slightly higher constant factor overhead from heap operations.
### Explanation
This approach optimizes the simulation by using priority queues (min-heaps) to efficiently manage room states. We use two heaps:

1.  `availableRooms`: A min-heap storing the indices of rooms that are currently free. Being a min-heap, it allows us to retrieve the available room with the lowest index in `O(log N)` time.
2.  `occupiedRooms`: A min-heap storing pairs of `(endTime, roomIndex)`. It is ordered by `endTime`, enabling us to find out which occupied room will become free next in `O(log N)` time.

As with the naive approach, we start by sorting meetings by their start time. We initialize `availableRooms` with all room indices from `0` to `n-1`.

We then iterate through the sorted meetings. For each meeting `[start, end]`:

First, we advance our simulation time to `start`. We check the `occupiedRooms` heap for any rooms that should have become free by now (i.e., their `endTime <= start`). We poll all such rooms and add their indices back into the `availableRooms` heap.

Next, we need to schedule the current meeting. We check if `availableRooms` is empty. 
- If it's not empty, we have at least one free room. We poll from `availableRooms` to get the one with the lowest index. We schedule the meeting in this room, which means we add a new entry `(end, roomIndex)` to the `occupiedRooms` heap and increment the room's meeting count.
- If `availableRooms` is empty, all rooms are busy. The meeting is delayed. It must wait for the next available slot. This slot is determined by the room at the top of the `occupiedRooms` heap (the one with the earliest `endTime`). We poll this room `(earliestFreeTime, roomIndex)`. The current meeting will start at `earliestFreeTime`. Its duration is `end - start`, so its new end time is `earliestFreeTime + (end - start)`. We add `(newEndTime, roomIndex)` back to `occupiedRooms` and update the meeting count.

After processing all meetings, we find the room with the highest meeting count to return as the result.

```java
import java.util.Arrays;
import java.util.PriorityQueue;

class Solution {
    public int mostBooked(int n, int[][] meetings) {
        Arrays.sort(meetings, (a, b) -> Integer.compare(a[0], b[0]));

        // Min-heap to store available room numbers
        PriorityQueue<Integer> availableRooms = new PriorityQueue<>();
        for (int i = 0; i < n; i++) {
            availableRooms.add(i);
        }

        // Min-heap to store occupied rooms, sorted by end time.
        // Stores {endTime, roomNumber}
        PriorityQueue<long[]> occupiedRooms = new PriorityQueue<>((a, b) -> {
            if (a[0] != b[0]) {
                return Long.compare(a[0], b[0]);
            }
            return Long.compare(a[1], b[1]); // Tie-break by room number
        });

        int[] meetingCounts = new int[n];

        for (int[] meeting : meetings) {
            long start = meeting[0];
            long end = meeting[1];

            // Free up rooms that have finished their meetings by the current start time
            while (!occupiedRooms.isEmpty() && occupiedRooms.peek()[0] <= start) {
                long[] freedRoom = occupiedRooms.poll();
                availableRooms.add((int) freedRoom[1]);
            }

            if (!availableRooms.isEmpty()) {
                // An available room exists, use the one with the smallest index
                int roomToUse = availableRooms.poll();
                occupiedRooms.add(new long[]{(long)end, roomToUse});
                meetingCounts[roomToUse]++;
            } else {
                // No rooms are available, delay the meeting
                // Get the room that will be free the earliest
                long[] nextFreeRoom = occupiedRooms.poll();
                long earliestFreeTime = nextFreeRoom[0];
                int roomToUse = (int) nextFreeRoom[1];
                
                long duration = end - start;
                long newEndTime = earliestFreeTime + duration;
                
                occupiedRooms.add(new long[]{newEndTime, roomToUse});
                meetingCounts[roomToUse]++;
            }
        }

        int maxMeetings = -1;
        int resultRoom = -1;
        for (int i = 0; i < n; i++) {
            if (meetingCounts[i] > maxMeetings) {
                maxMeetings = meetingCounts[i];
                resultRoom = i;
            }
        }
        return resultRoom;
    }
}
```
### Algorithm
* Sort the `meetings` array by start time.
* Initialize a min-heap `availableRooms` with all room indices from `0` to `n-1`.
* Initialize an empty min-heap `occupiedRooms` to store pairs `(endTime, roomIndex)`, ordered by `endTime`.
* Initialize a `meetingCounts` array of size `n` with zeros.
* For each `meeting [start, end]` in the sorted list:
  * Free up any rooms in `occupiedRooms` that have an `endTime` less than or equal to the current meeting's `start` time. Move their indices to `availableRooms`.
  * If `availableRooms` is not empty, poll the lowest-indexed room. Schedule the meeting there, update its count, and add `(end, roomIndex)` to `occupiedRooms`.
  * If `availableRooms` is empty, the meeting is delayed. Poll the earliest-finishing room from `occupiedRooms`. Calculate the new end time based on the room's free time and meeting duration. Update its count and add the new `(newEndTime, roomIndex)` back to `occupiedRooms`.
* After processing all meetings, find the room index with the maximum count, breaking ties by choosing the smaller index.

# Solutions
### Java

```java
class Solution {
public
  int mostBooked(int n, int[][] meetings) {
    Arrays.sort(meetings, (a, b)->a[0] - b[0]);
    PriorityQueue<int[]> busy =
        new PriorityQueue<>((a, b)->a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
    PriorityQueue<Integer> idle = new PriorityQueue<>();
    for (int i = 0; i < n; ++i) {
      idle.offer(i);
    }
    int[] cnt = new int[n];
    for (var v : meetings) {
      int s = v[0], e = v[1];
      while (!busy.isEmpty() && busy.peek()[0] <= s) {
        idle.offer(busy.poll()[1]);
      }
      int i = 0;
      if (!idle.isEmpty()) {
        i = idle.poll();
        busy.offer(new int[]{e, i});
      } else {
        var x = busy.poll();
        i = x[1];
        busy.offer(new int[]{x[0] + e - s, i});
      }
      ++cnt[i];
    }
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      if (cnt[ans] < cnt[i]) {
        ans = i;
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
using ll = long long ; using pii = pair < ll , int > ; class Solution { public: int mostBooked ( int n , vector < vector < int >>& meetings ) { priority_queue < int , vector < int > , greater < int >> idle ; priority_queue < pii , vector < pii > , greater < pii >> busy ; for ( int i = 0 ; i < n ; ++ i ) idle . push ( i ); vector < int > cnt ( n ); sort ( meetings . begin (), meetings . end ()); for ( auto & v : meetings ) { int s = v [ 0 ], e = v [ 1 ]; while ( ! busy . empty () && busy . top (). first <= s ) { idle . push ( busy . top (). second ); busy . pop (); } int i = 0 ; if ( ! idle . empty ()) { i = idle . top (); idle . pop (); busy . push ({ e , i }); } else { auto x = busy . top (); busy . pop (); i = x . second ; busy . push ({ x . first + e - s , i }); } ++ cnt [ i ]; } int ans = 0 ; for ( int i = 0 ; i < n ; ++ i ) { if ( cnt [ ans ] < cnt [ i ]) { ans = i ; } } return ans ; } };
```

### Python

```python
class Solution:
    def mostBooked(self, n: int, meetings: List[List[int]]) -> int: meetings . sort() busy = [] idle = list(range(n)) heapify(idle) cnt = [0] * n for s, e in meetings: while busy and busy[0][0] <= s: heappush(idle, heappop(busy)[1]) if idle: i = heappop(idle) cnt[i] += 1 heappush(busy, (e, i)) else: a, i = heappop(busy) cnt[i] += 1 heappush(busy, (a + e - s, i)) ans = 0 for i, v in enumerate(cnt): if cnt[ans] < v: ans = i return ans

```