Busiest Room
MediumHeap / Priority Queue
Problem
A coworking space has n rooms numbered 0 to n - 1. Each meetings[i] = [start, end] asks for a room during the half-open interval [start, end); all start times are distinct. Meetings are handled in order of their original start time:
If any room is free at the meeting's start, it gets the free room with the lowest number. Otherwise it is delayed until the earliest moment a room frees up (lowest number among rooms freeing at that same moment) and keeps its original duration. When a delayed meeting and a later meeting compete, the one with the earlier original start goes first.
Return the number of the room that hosted the most meetings; on a tie, the lowest room number.
Example 1
- Input:
- n = 2, meetings = [[0, 10], [1, 5], [2, 7], [3, 4]]
- Output:
- 0
Room 0 takes [0,10), room 1 takes [1,5). [2,7) waits for room 1 at 5 → [5,10). [3,4) waits for 10; both rooms free at 10, room 0 wins → [10,11). Room 0 hosted 2, room 1 hosted 2 → tie → 0.
Example 2
- Input:
- n = 3, meetings = [[1, 20], [2, 10], [3, 5], [4, 9], [6, 8]]
- Output:
- 1
Constraints
- 1 ≤ n ≤ 100
- 1 ≤ meetings.length ≤ 10^5
- 0 ≤ start < end ≤ 5·10^5
- All start times are distinct.
Hint
Show the first hint
Sort meetings by start. At each start, which rooms have become free since the last meeting?
Walkthrough
How to approach it
01Clarify before coding
- Does a delayed meeting keep its duration? Yes, it is shifted, not shortened.
- Are start times distinct? Yes, so the processing order is unambiguous.
- Tie on the busiest count? Lowest room number.
02Brute force
For each meeting, scan all n rooms for a free one or for the earliest end time.
Cost: O(m · n) = 10^7 here: acceptable for n ≤ 100, but it scales badly if rooms grow, and the heap version is the expected answer.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.