911. Which Room Was Busiest

A building has rooms numbered 0 to r-1. n meetings each have a start and an end time, and all starts are distinct. Meetings are allocated in increasing order of their ORIGINAL start time by this rule:

if any room is free at that moment, use the LOWEST-numbered free room otherwise wait for the room that frees up EARLIEST, ties going to the lower number, and hold the meeting there, delayed but keeping its original duration

Print the number of the room that held the most meetings; if several tie, print the lowest such number.

r = 2, meetings (0,10) (1,5) (2,7) (3,4) -> 0 r = 2, meetings (0,100) (1,2) (3,4) (5,6) -> 1 r = 3, one meeting (5,9) -> 0

The first one is worth working through, because every branch of the rule fires.

(0,10) both rooms free, take room 0, which is busy until 10 (1,5) room 1 is free, take it, busy until 5 (2,7) both busy at time 2; room 1 frees first, at 5. The meeting is 5 units long, so it runs 5 to 10 in room 1. (3,4) both busy at time 3, room 0 until 10 and room 1 until 10 as well. The tie goes to the lower number, so room 0 runs it 10 to 11.

Room 0 held two meetings and room 1 held two, a tie, so the answer is 0.

In the second example room 0 is tied up for a hundred minutes on its first meeting while room 1 takes the other three, so the answer is 1.

## What most people try first

An array of "when is this room free" scanned on every meeting is O(n r). With r = 100 and n = 10^5 that is 10^7 and survives; with r raised it does not, and more importantly the scan hides the structure. The point of this problem is that there are TWO questions, and each one wants its own heap.

## The method: two heaps, and neither is a median

free a min-heap of ROOM NUMBERS, the rooms available right now busy a min-heap of (end time, room number), the rooms in use

sort meetings by start for each (s, e): while busy is non-empty and its smallest end time <= s: move that room from busy into free if free is non-empty: room = pop free; push (e, room) onto busy else: (t, room) = pop busy; push (t + (e - s), room) onto busy count[room] = count[room] + 1 answer = the lowest room number with the largest count

The two heaps are ordered by different things, which is the whole idea. The free pool is ordered by room NUMBER because the rule says lowest-numbered wins. The busy pool is ordered by END TIME because the rule says earliest-freeing wins, with the room number as the tie-break inside the pair.

## Why it is correct

The rule is stated operationally, so correctness here means faithfully implementing it rather than proving an optimum, and the only thing to argue is that the release loop is complete.

Meetings are processed in increasing start time. So when meeting (s, e) is considered, every room whose end time is at most s is genuinely free, and every such room is at the top of busy before any room that is still occupied. Draining the busy heap while its top ends at or before s therefore releases exactly the right set, and it does so in amortised constant time per room because each room enters busy once per meeting.

The delayed case keeps the DURATION, not the end time. e - s is the length of the meeting, and the new end is the room's free time plus that length.

## The boundary that breaks a careless implementation

A room freeing exactly AT s is free: the comparison is end <= s. Writing < pushes a meeting into the delayed branch when a room was available, and the delay then cascades through every later meeting.

The tie-break in busy must be on the room number, not on insertion order. Two rooms freeing at the same instant must hand the meeting to the lower-numbered one, and a heap of bare end times cannot express that.

The final answer is the LOWEST room number among those with the largest count, so the scan over counts must use a strict comparison and start from room 0.

## Overflow

End times are where this bites. A start is at most 10^9 and a duration at most 10^9, but delays accumulate: with one room and 10^5 meetings of 10^9 each, the last end time is about 10^14.

Even the small declared test with two rooms and six meetings pushes an end time to 3 * 10^9. A 32-bit clock wraps that to a NEGATIVE number, the room then looks free at every later start, and the answer changes from 0 to 1. Hold the end times in 64 bits.

## Related problems

Problem #277 asks how many rooms are needed so that nothing ever waits, and answers it with two sorted lists and a sweep, no heap at all. This problem fixes the number of rooms and asks what actually happens, which forces the identity of each room to be tracked and is why a counting sweep is not enough.

## Cost

Time O(n log n + n log r). Space O(n + r).

Constraints - `1 ≤ r ≤ 100` - `1 ≤ n ≤ 100000` - `0 ≤ start < end ≤ 10^9` - All start times are distinct.