Most Used Meeting Room When Meetings Wait for a Free Room
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
A building has `n` meeting rooms numbered `0` to `n - 1`. You are given a list of meetings, each with a start time and an end time, and no two meetings have the same start time. Meetings are assigned to rooms by the rules below; when no room is free, a meeting is delayed rather than dropped. Return the number of the room that hosts the most meetings.
The report names this as a variant of a known room-scheduling problem without saying what the variant changed; this statement uses the standard rules.
### Function Signature
```python
def most_used_room(n: int, meetings: list[list[int]]) -> int:
```
### Rules
- `meetings[i] = [start, end]` needs one room for the half-open interval `[start, end)`. A room whose meeting ends at time `t` can host a meeting that starts at time `t`.
- Meetings are assigned one at a time, in increasing order of their original start times.
- If one or more rooms are free at a meeting's start time, the meeting takes the free room with the lowest number.
- If no room is free, the meeting is delayed until the earliest time at which a room becomes free, and takes the lowest-numbered room that becomes free at that time. A delayed meeting keeps its original duration `end - start`.
- Every meeting is eventually held; none is dropped.
- Return the room that hosts the most meetings. If several rooms tie, return the lowest room number.
### Constraints
- `1 <= n <= 100`
- `1 <= len(meetings) <= 10^5`
- `0 <= start < end <= 5 * 10^5` for every meeting
- All `start` values are distinct; `meetings` may be given in any order.
- Delays accumulate, so a delayed meeting can end as late as about `5 * 10^10`, which exceeds `2^31 - 1`. Use 64-bit integers for times; every value stays well below `2^53`.
### Examples
**Example 1**
```text
Input: n = 2, meetings = [[0, 10], [1, 3], [2, 4], [5, 6]]
Output: 1
```
Room 0 takes `[0, 10)` and room 1 takes `[1, 3)`. At time 2 both rooms are busy, so `[2, 4)` waits for room 1, which frees at 3, and runs as `[3, 5)`. At time 5 room 1 is free again and takes `[5, 6)`. Room 1 hosts three meetings and room 0 hosts one.
**Example 2**
```text
Input: n = 3, meetings = [[1, 4], [2, 3], [3, 7], [4, 5]]
Output: 0
```
`[1, 4)` takes room 0 and `[2, 3)` takes room 1. At time 3 rooms 1 and 2 are free, so `[3, 7)` takes room 1. At time 4 rooms 0 and 2 are free, so `[4, 5)` takes room 0. Rooms 0 and 1 each host two meetings, and the tie goes to room 0.
**Example 3**
```text
Input: n = 2, meetings = [[0, 5], [3, 6], [2, 4], [1, 5], [8, 9]]
Output: 0
```
In start order, `[0, 5)` takes room 0 and `[1, 5)` takes room 1. `[2, 4)` must wait; both rooms become free at 5, so it takes room 0 and runs as `[5, 7)`. `[3, 6)` waits for room 1, free at 5, and runs as `[5, 8)`. At time 8 both rooms are free, so `[8, 9)` takes room 0. Room 0 hosts three meetings and room 1 hosts two.
Overview: A coding question about assigning meetings to numbered rooms: each meeting takes the lowest-numbered free room or waits for the earliest room to free up while keeping its duration, and the answer is the room that hosts the most meetings. It tests event simulation, exact tie-breaking and time values that exceed 32 bits.
A building has `n` meeting rooms numbered `0` to `n - 1`. You are given a list `meetings` where `meetings[i] = [start, end]` describes a meeting that needs one room for the half-open interval `[start, end)`. No two meetings share a start time, and `meetings` may be given in any order.
Meetings are assigned to rooms by these rules:
- Meetings are assigned one at a time, in increasing order of their original start times.
- A room whose meeting ends at time `t` can host a meeting that starts at time `t`.
- If one or more rooms are free at a meeting's start time, the meeting takes the free room with the lowest number.
- If no room is free, the meeting is delayed until the earliest time at which a room becomes free, and it takes the lowest-numbered room that becomes free at that time. A delayed meeting keeps its original duration `end - start`.
- Every meeting is eventually held; none is dropped.
Return the number of the room that hosts the most meetings. If several rooms tie, return the lowest room number.
Implement `most_used_room(n, meetings)`, which returns that room number as an integer.
### Constraints
- `1 <= n <= 100`
- `1 <= len(meetings) <= 10^5`
- `0 <= start < end <= 5 * 10^5` for every meeting
- All `start` values are distinct; `meetings` may be given in any order.
- Delays accumulate, so a delayed meeting can end as late as about `5 * 10^10`, which exceeds `2^31 - 1`. Use 64-bit integers for times (`long` in Java, `long long` in C++); every value stays well below `2^53`. The input times and the returned room number fit in 32-bit integers.
### Example 1
```text
Input: n = 2, meetings = [[0, 10], [1, 3], [2, 4], [5, 6]]
Output: 1
```
Room 0 takes `[0, 10)` and room 1 takes `[1, 3)`. At time 2 both rooms are busy, so `[2, 4)` waits for room 1, which frees at 3, and runs as `[3, 5)`. At time 5 room 1 is free again and takes `[5, 6)`. Room 1 hosts three meetings and room 0 hosts one.
### Example 2
```text
Input: n = 2, meetings = [[0, 5], [3, 6], [2, 4], [1, 5], [8, 9]]
Output: 0
```
In start order, `[0, 5)` takes room 0 and `[1, 5)` takes room 1. `[2, 4)` must wait; both rooms become free at 5, so it takes room 0 and runs as `[5, 7)`. `[3, 6)` waits for room 1, free at 5, and runs as `[5, 8)`. At time 8 both rooms are free, so `[8, 9)` takes room 0. Room 0 hosts three meetings and room 1 hosts two.
Constraints
- 1 <= n <= 100
- 1 <= len(meetings) <= 10^5
- 0 <= start < end <= 5 * 10^5 for every meeting [start, end]
- All start values are distinct; meetings may be given in any order.
- A delayed meeting can end as late as about 5 * 10^10, which exceeds 2^31 - 1: use 64-bit integers for times (long in Java, long long in C++); every value stays well below 2^53.
Examples
Input: (1, [[0, 1]])
Expected Output: 0
Explanation: Minimum valid input: one room and one meeting, so room 0 hosts it.
Input: (5, [[3, 8]])
Expected Output: 0
Explanation: A single meeting with five free rooms takes the lowest-numbered free room, 0.
Hints
- Meetings are handled in increasing order of their original start times, not in the order they are given.
- For each room it is enough to know the time it next becomes free; a room that frees exactly at a meeting's start time counts as free.
- A meeting that has to wait starts when its room frees and keeps its original duration, so its new end can grow far beyond the input times.