525. Exam Room
An exam room has a single row of n seats numbered 0 through n - 1. Students trickle in one at a time, and each new student is antisocial in a very precise way: they take the seat that maximizes the distance to the closest seated student. If several seats are tied for that distance, they take the one with the lowest seat number. A student entering an empty room sits at seat 0.
Design a class ExamRoom supporting two operations:
seat()— a student enters; return the seat number they take (and mark it occupied).leave(p)— the student in seatpwalks out (seatpis guaranteed to be occupied).
The interesting part is doing this efficiently when n is huge (up to 10^9) — you can never afford an array over all seats.
Example 1:
Input: ExamRoom(10); seat(); seat(); seat(); seat(); leave(4); seat()
Output: 0, 9, 4, 2, 5
Explanation: Seat 0 (empty room), then seat 9 (as far from 0 as possible), then seat 4 (middle of the 0–9 gap, distance 4; seat 5 also has distance 4 but 4 is lower). The fourth student sees ties at distance 2 (seats 2 and 6) and takes 2. After the student at 4 leaves, the widest gap is 2–9, so the next student sits at its midpoint, 5.
Example 2:
Input: ExamRoom(4); seat(); seat(); seat(); leave(0); seat()
Output: 0, 3, 1, 0
Explanation: 0, then 3, then 1 (seats 1 and 2 both sit at distance 1 from their nearest neighbor; 1 is lower). When seat 0 frees up, the best distance anywhere is again 1 — from seat 0 (next to 1) or seat 2 (between 1 and 3) — and 0 is the lower seat.
Constraints:
- 1 ≤ n ≤ 10⁹
- 0 ≤ p < n; leave(p) is only called on an occupied seat
- seat() is only called when at least one seat is free
- At most 10⁴ calls total to seat and leave
Hints:
Only the occupied seats matter, never all n. Between two neighboring occupied seats a and b, the best seat inside is the midpoint a + (b - a) / 2 with distance (b - a) / 2 — and the two ends of the row are special: seat 0's distance is just the first occupied seat's index, seat n-1's is n-1 minus the last one.
Simple version: keep the occupied seats in sorted order and, on each seat(), scan all the gaps for the best candidate. That is O(m) per call — fine for 10^4 operations.
Faster: treat every gap between neighbors as an object with a score, and keep gaps in a max-heap keyed by (distance, then lower seat). leave(p) merges two gaps into one, which would mean deleting from the heap — instead push the merged gap and lazily skip any popped gap whose endpoints are no longer adjacent (track neighbors with two hash maps).
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: ExamRoom(10); seat(); seat(); seat(); seat(); leave(4); seat()
Expected output: 0, 9, 4, 2, 5