Assign Meetings and Find the Most-Used Room
Company: ByteDance
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
# Assign Meetings and Find the Most-Used Room
There are `n` rooms numbered from `0` through `n - 1` and meetings `[start, end]` with distinct start times. Process meetings by increasing start time.
- If one or more rooms are free at a meeting's start, assign the available room with the smallest number.
- If no room is free, delay the meeting until the earliest room becomes free, preserving the meeting's original duration. If several rooms become free at that earliest time, use the smallest room number.
Return the room that hosts the most meetings. Break a count tie by returning the smallest room number.
## Function Signature
```python
def most_used_room(n: int, meetings: list[list[int]]) -> int:
...
```
## Constraints
- `1 <= n <= 100_000`
- `1 <= len(meetings) <= 200_000`
- `0 <= start < end <= 1_000_000_000`
- Meeting start times are pairwise distinct.
- Delayed end times may exceed the largest original end time. Under these input bounds, every delayed time remains below `201_000_000_000_000`, within the exact integer range shared by the supported runtimes.
## Example
```text
Input: n = 2, meetings = [[0, 10], [1, 5], [2, 7], [3, 4]]
Output: 0
```
```text
Input: n = 3, meetings = [[1, 20], [2, 10], [3, 5], [4, 9], [6, 8]]
Output: 1
```
Overview: Practice an interval-scheduling problem where meetings may be delayed and room-number tie rules affect the final count. The prompt tests precise simulation, large-input complexity, integer safety, and careful handling of simultaneous room availability.
You are given an integer `n`, the number of meeting rooms, numbered `0` through `n - 1`, and a list `meetings` where `meetings[i] = [start_i, end_i]` describes a meeting that wants to run over the half-open interval `[start_i, end_i)`. All start times are pairwise distinct, but `meetings` is **not** guaranteed to be given in sorted order.
Process the meetings in increasing order of start time. A room is free at time `t` if no meeting is occupying it, or if the meeting occupying it ends at a time less than or equal to `t`. For each meeting in turn:
- If at least one room is free at the meeting's start time, hold the meeting in the free room with the **smallest number**. It occupies that room over `[start_i, end_i)`.
- If no room is free, delay the meeting until the earliest time any room becomes free. A delayed meeting keeps its original duration `end_i - start_i`, so if the chosen room frees at time `f` the meeting occupies `[f, f + (end_i - start_i))`. If several rooms become free at that same earliest time `f`, use the one with the **smallest number**.
A room's meeting count is the number of meetings it hosts, whether they started on time or were delayed.
Return the number of the room that hosts the most meetings. If several rooms are tied for the most meetings, return the **smallest** such room number.
**Output semantics.** Return a single integer: a room number in `[0, n - 1]`. Every choice above resolves ties by smallest room number, so exactly one answer is correct for any valid input.
**Note on magnitudes.** Delaying meetings pushes end times past the largest original end time. Under the constraints below every time value stays below `201000000000000` (about `2.01 * 10^14`), which exceeds the range of a 32-bit signed integer. Java implementations must accumulate these times in `long` and C++ implementations in `long long`; the room numbers and the returned value still fit in `int`.
### Example 1
```text
Input: n = 2, meetings = [[0, 10], [1, 5], [2, 7], [3, 4]]
Output: 0
```
- `[0, 10)` starts first and takes room 0, which is then busy until 10.
- `[1, 5)` finds room 0 busy and takes room 1, busy until 5.
- `[2, 7)` finds both rooms busy. Room 1 frees earliest, at time 5. The meeting keeps its duration of 5 and runs `[5, 10)` in room 1.
- `[3, 4)` finds both rooms busy, and both free at time 10. The smaller number wins, so it runs `[10, 11)` in room 0.
Room 0 hosts 2 meetings and room 1 hosts 2 meetings. The counts are tied, so the smaller room number is returned: `0`.
### Example 2
```text
Input: n = 3, meetings = [[1, 20], [2, 10], [3, 5], [4, 9], [6, 8]]
Output: 1
```
- `[1, 20)` takes room 0, `[2, 10)` takes room 1, and `[3, 5)` takes room 2.
- `[4, 9)` finds every room busy. Room 2 frees earliest, at time 5, so the meeting keeps its duration of 5 and runs `[5, 10)` in room 2.
- `[6, 8)` finds every room busy. Rooms 1 and 2 both free at time 10, so the smaller number wins and the meeting runs `[10, 12)` in room 1.
Room 0 hosts 1 meeting, room 1 hosts 2, and room 2 hosts 2. Rooms 1 and 2 are tied for the most, so the smaller room number is returned: `1`.
Constraints
- 1 <= n <= 100000
- 1 <= meetings.length <= 200000
- meetings[i].length == 2
- 0 <= start_i < end_i <= 10^9
- All start_i are pairwise distinct.
- Delayed end times may exceed the largest original end time, but under these bounds every time value stays below 201000000000000 (about 2.01 * 10^14), so Java must use long and C++ must use long long for time arithmetic.
Examples
Input: (2, [[0,10],[1,5],[2,7],[3,4]])
Expected Output: 0
Input: (3, [[1,20],[2,10],[3,5],[4,9],[6,8]])
Expected Output: 1
Hints
- The input array is not sorted. Every rule in the statement is phrased in terms of increasing start time, so the very first thing to fix is the processing order.
- At each step you need two different 'minimums': the smallest-numbered idle room, and among the busy rooms the one that frees earliest (smallest number on a tie). Keeping two separate priority queues gives you both in logarithmic time instead of scanning all n rooms.
- A delayed meeting is not truncated to its original end. Its new end is the time the room frees plus its original duration, and those sums keep growing as delays chain, so pick a wide enough integer type for them.