Busiest Meeting Room

A co-working space has n meeting rooms numbered 0 to n - 1. Each meeting (start, end) wants a room from time start up to time end (a room that frees up at time t can take a meeting that starts at t). Every start time is different, and meetings are handed out in order of start time by these rules:

• A meeting takes the free room with the lowest number.
• If no room is free, the meeting waits for the first room to free up and then takes it, keeping its length: a meeting of length 5 that starts late still lasts 5.
• If several rooms free up at the same moment, a waiting meeting takes the lowest-numbered of them. Waiting meetings are served in order of their original start time.

Write busiest_room(n, meetings) that returns the number of the room that hosted the most meetings. If several rooms tie, return the lowest number.

Examples

busiest_room(2, [(0, 10), (1, 5), (2, 7), (3, 4)])
# returns 0

busiest_room(3, [(1, 20), (2, 10), (3, 5), (4, 9), (6, 8)])
# returns 1

In the first example room 0 takes the meeting at 0 and room 1 the meeting at 1. The meeting that wanted to start at 2 waits for room 1, which frees up at 5, and runs from 5 to 10. The meeting that wanted to start at 3 waits until 10, when both rooms free up, and takes room 0. Each room hosted two meetings, so the answer is 0.

Constraints

• 1 <= n <= 10,000
• 1 <= len(meetings) <= 100,000, given in any order
• 0 <= start < end <= 10^9, and all start times are different
• With thousands of rooms, checking every room for every meeting is too slow.