Exam Room - Solution & Explanation

Problem Overview: You manage an exam room with n seats numbered 0 to n-1. Each arriving student chooses a seat that maximizes the distance to the closest occupied seat. If multiple seats give the same distance, the student picks the smallest index. You must implement seat() and leave(p) efficiently.

Approach 1: Sorted List of Occupied Seats (O(n) seat, O(n) leave)

This approach maintains a sorted list (or ordered set) of occupied seat indices. When a student calls seat(), iterate through the sorted seats and compute the largest possible distance between adjacent occupied seats. Also check the edges: the distance from seat 0 to the first student and from the last student to n-1. The best candidate seat is either the midpoint between two occupied seats or an edge seat. Insert the chosen seat into the sorted structure and maintain order.

The key idea is that the optimal seat always lies either at the midpoint of the largest gap or at a boundary. Computing the midpoint of each gap requires scanning the occupied list, which takes O(n) time. Insertion or deletion in a list also costs O(n). Space complexity is O(n) because you store all occupied seats. This approach is straightforward and easy to implement, especially in Python with a list or in C++ with an ordered container from Ordered Set.

Approach 2: Maximum Heap of Intervals (O(log n) seat, O(log n) leave)

A more scalable design models the room as intervals of empty seats. Each interval represents the gap between two occupied seats, such as (left, right). The best seat inside an interval is the midpoint that maximizes the distance to neighbors. Store intervals in a max heap ordered by their effective seating distance (largest first), with ties broken by smaller seat index.

When seat() runs, extract the largest interval from the heap. Compute the optimal seat inside it, then split the interval into two new intervals and push them back into the heap. When leave(p) runs, merge the two intervals adjacent to seat p into a larger interval and update the heap. Efficient merging usually requires hash maps that track interval boundaries.

This design relies on a Heap (Priority Queue) to always retrieve the largest gap in O(log n) time. Both seating and leaving operations maintain interval structure with heap updates. Space complexity remains O(n). The approach demonstrates strong Design skills because you model the room as dynamic segments rather than raw seat indices.

Recommended for interviews: Start by explaining the sorted list approach to show the greedy insight that students always sit in the largest gap. Then present the interval heap design as the optimized solution. Interviewers typically expect the heap-based design because it reduces repeated scans and keeps operations near O(log n), which scales well when many seat and leave operations occur.