Practice/Apple/Leetcode 855. Exam Room

Leetcode 855. Exam Room

CodingMust

Problem

Design a seating system for a concert hall with n seats arranged in a single row, numbered from 0 to n-1.

When someone arrives and calls seat(), they should be assigned to the seat that maximizes the distance to the closest already-occupied seat. If there are multiple such seats, choose the one with the smallest index.

When someone leaves and calls leave(p), seat p becomes available again.

Your task is to implement the ConcertHall class with these methods:

• ConcertHall(n): Initializes a concert hall with n seats, all initially empty
• seat(): Returns the seat number where the next person should sit
• leave(p): Marks seat p as empty

Requirements

1. The first person always sits at seat 0
2. When all seats are empty except one, the next person sits at seat n-1 (farthest position)
3. Subsequent people sit at positions that maximize distance to nearest occupied seat
4. Break ties by choosing the smallest seat number
5. Handle up to 10,000 total operations efficiently
6. Support very large values of n (up to 10^9)

Constraints

• 1 ≤ n ≤ 10^9
• At most 10^4 calls total to seat() and leave()
• leave(p) will only be called on an occupied seat
• You will never try to seat someone when all n seats are full

Examples

Example 1:

ConcertHall hall = ConcertHall(10); hall.seat(); // Returns 0 (first person sits at leftmost seat) hall.seat(); // Returns 9 (maximize distance from 0) hall.seat(); // Returns 4 (middle of gap between 0 and 9) hall.leave(4); // Seat 4 becomes empty hall.seat(); // Returns 4 (again the optimal position)

Example 2:

ConcertHall hall = ConcertHall(8); hall.seat(); // Returns 0 hall.seat(); // Returns 7 hall.seat(); // Returns 3 (middle of 0-7, distance 3 to nearest) hall.seat(); // Returns 5 (middle of 3-7, distance 2; also middle of 0-3 is 1 with distance 1) hall.leave(3); // Seat 3 becomes empty hall.seat(); // Returns 3 (recreates the gap)