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

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

Input: n = 2, meetings = [[0, 10], [1, 5], [2, 7], [3, 4]]
Output: 0

Input: n = 3, meetings = [[1, 20], [2, 10], [3, 5], [4, 9], [6, 8]]
Output: 1

Busiest Room Under Delayed Meeting Scheduling

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

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

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.

Hints

1. 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.
2. 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.
3. 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.

Approach

The statement fixes a total processing order (increasing start time, and starts are distinct), so the assignment is a deterministic simulation. The only question is how to run each step in better than O(n) time.

Sort the meetings by start time, then maintain two min-heaps:

• free, holding the numbers of idle rooms, ordered by room number.
• busy, holding (free_at, room) pairs, ordered by release time and then by room number.

Before handling a meeting that starts at start, pop every entry of busy whose free_at <= start and push its room back into free. This is where the half-open interval matters: a room whose meeting ends exactly at start counts as available, so the comparison must be <=, not <.

Then there are two cases. If free is non-empty, pop its minimum, which is the smallest-numbered idle room, and push (end, room) onto busy. If free is empty, pop the minimum of busy; because the pairs are ordered by (free_at, room), that pop resolves both required tie-breaks at once, giving the earliest release time and the smallest room number among the rooms sharing it. The delayed meeting preserves its duration, so it is re-pushed as (free_at + (end - start), room).

Either way, increment the chosen room's counter. At the end, scan the counters once and keep the first index achieving the maximum, which returns the smallest room number on a tie.

Each meeting causes at most one push and one pop on each heap, so the simulation is O(m log n) on top of the O(m log m) sort, where m is the number of meetings.

The one non-obvious hazard is arithmetic width. Inputs fit comfortably in 32 bits because end_i <= 10^9, but delays accumulate: with n small and many long meetings, free_at climbs toward 2 * 10^14. A 32-bit accumulator wraps to a negative value, which then looks like the earliest-freeing room and corrupts every later assignment. Java needs long and C++ needs long long for the time fields; JavaScript numbers are exact well past 2 * 10^14, and Python integers are unbounded.

• Time complexity: O(m log m + m log n) where m = meetings.length
• Space complexity: O(n + m)