An office has n meeting rooms, numbered 0 to n - 1. Each meeting is [start, end]: it wants a room from start up to, but not including, end. No two meetings share a start time. Rooms are handed out like this:
- Meetings are handled in order of their start time (the input list can be in any order).
- A meeting takes the lowest-numbered room that is free at its start. A room that frees up at time
tcounts as free for a meeting starting att. - If no room is free, the meeting waits and starts as soon as a room frees up, keeping its original length. If several rooms free up at that same moment, it takes the lowest-numbered one. Meetings that are waiting get rooms in order of their original start time.
Write busiest_room(n: int, meetings: list[list[int]]) -> int that returns the room that hosted the most meetings. On a tie, return the lowest room number.
busiest_room(2, [[4, 6], [0, 3], [1, 9], [2, 5]])
# 0 [0,3) room 0, [1,9) room 1, [2,5) waits for room 0 and runs [3,6),
# [4,6) waits for room 0 again and runs [6,8): room 0 hosts 3 meetings
busiest_room(3, [[0, 8], [1, 3], [2, 4], [3, 9], [5, 6]])
# 1 rooms host 1, 2 and 2 meetings; room 1 wins the tie
busiest_room(4, [[5, 6]])
# 0
Constraints: 1 <= n <= 10^5, 1 <= len(meetings) <= 10^5, 0 <= start < end <= 5 * 10^5. Waiting can push meetings far past 5 * 10^5 (beyond 32-bit range), so use 64-bit integers in C++ and Java.
Scanning all n rooms for every meeting is O(n · m) and fails the large tests. Aim for O((n + m) log(n + m)).
Show hint
Two questions come up for every meeting: "which free room has the lowest number?" and "which busy room frees up first (lowest number on a tie)?". Keep one ordered collection for each, and move rooms between them as time passes.