# Exam Room
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/exam-room)
Canonical: https://scaleengineer.com/dsa/problems/exam-room
**Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design)
**Data structures:** Heap (Priority Queue), Ordered Set
**Companies:** [Quora](https://scaleengineer.com/companies/quora)
---
## Problem
There is an exam room with `n` seats in a single row labeled from `0` to `n - 1`.

When a student enters the room, they must sit in the seat that maximizes the distance to the closest person. If there are multiple such seats, they sit in the seat with the lowest number. If no one is in the room, then the student sits at seat number `0`.

Design a class that simulates the mentioned exam room.

Implement the `ExamRoom` class:

* `ExamRoom(int n)` Initializes the object of the exam room with the number of the seats `n`.
* `int seat()` Returns the label of the seat at which the next student will set.
* `void leave(int p)` Indicates that the student sitting at seat `p` will leave the room. It is guaranteed that there will be a student sitting at seat `p`.

**Example 1:**

**Input**
["ExamRoom", "seat", "seat", "seat", "seat", "leave", "seat"]
[[10], [], [], [], [], [4], []]
**Output**
[null, 0, 9, 4, 2, null, 5]

**Explanation**
ExamRoom examRoom = new ExamRoom(10);
examRoom.seat(); // return 0, no one is in the room, then the student sits at seat number 0.
examRoom.seat(); // return 9, the student sits at the last seat number 9.
examRoom.seat(); // return 4, the student sits at the last seat number 4.
examRoom.seat(); // return 2, the student sits at the last seat number 2.
examRoom.leave(4);
examRoom.seat(); // return 5, the student sits at the last seat number 5.

**Constraints:**

* `1 <= n <= 109`
* It is guaranteed that there is a student sitting at seat `p`.
* At most `104` calls will be made to `seat` and `leave`.

# Approaches
## Linear Scan with a Sorted List
This approach uses a simple `ArrayList` to store the positions of the students. To maintain the ability to find gaps between adjacent students, the list is kept sorted after every insertion.
**Time:** *   `seat()`: O(k log k). The loop to find the best gap takes O(k) time, and sorting the list after insertion takes O(k log k). 
*   `leave(p)`: O(k). Removing an element from an `ArrayList` requires a linear scan to find the element and shift subsequent elements. · **Space:** O(k), where k is the number of occupied seats (students in the room). We need to store the position of each student.
**Pros:** The logic is straightforward and relatively easy to implement and understand.; It works correctly for the given problem constraints on the number of calls, although it's not the most performant.
**Cons:** The `seat()` operation is inefficient because finding the best gap requires iterating through all occupied seats, which takes O(k) time. Inserting into a sorted list and re-sorting also takes O(k) time.; The `leave(p)` operation is also inefficient, as removing an element from an `ArrayList` takes O(k) time on average due to the need to shift elements.
### Explanation
The core idea is to maintain a sorted list of occupied seat numbers. When a new student needs to be seated, we can iterate through this list to find the largest empty segment (gap) and place the student in the middle of it.

### `seat()` operation:
When `seat()` is called, we analyze all possible places a student can sit. These places are determined by the gaps between existing students and the gaps at the ends of the row.
1.  **If the room is empty:** The first student sits at seat 0.
2.  **If the room has students:** We calculate the largest possible distance a new student can have from their nearest neighbor. This can be:
    *   At seat 0, with a distance of `seats.get(0)` from the first student.
    *   At seat `n-1`, with a distance of `(n-1) - seats.get(seats.size()-1)` from the last student.
    *   In the middle of any two adjacent students `p1` and `p2`. The best seat is `(p1+p2)/2`, with a distance of `(p2-p1)/2`.

We iterate through all these possibilities, find the one that maximizes the distance, and handle ties by choosing the lower seat number. After finding the best seat, we add it to our list and re-sort the list to prepare for the next call.

### `leave()` operation:
When `leave(p)` is called, we simply find and remove the seat `p` from our list.

```java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class ExamRoom {
    private List<Integer> seats;
    private int n;

    public ExamRoom(int n) {
        this.n = n;
        this.seats = new ArrayList<>();
    }
    
    public int seat() {
        if (seats.isEmpty()) {
            seats.add(0);
            return 0;
        }

        int maxDist = seats.get(0);
        int seat = 0;

        for (int i = 0; i < seats.size() - 1; ++i) {
            int p1 = seats.get(i);
            int p2 = seats.get(i + 1);
            int dist = (p2 - p1) / 2;
            if (dist > maxDist) {
                maxDist = dist;
                seat = p1 + dist;
            }
        }

        if (n - 1 - seats.get(seats.size() - 1) > maxDist) {
            seat = n - 1;
        }

        seats.add(seat);
        Collections.sort(seats);
        return seat;
    }
    
    public void leave(int p) {
        seats.remove(Integer.valueOf(p));
    }
}
```
### Algorithm
*   **Constructor `ExamRoom(n)`**:
    1.  Initialize an `ArrayList<Integer>` called `seats` to store the positions of occupied seats.
    2.  Store the total number of seats `n`.

*   **`seat()` method**:
    1.  If `seats` is empty, add `0` to `seats` and return `0`.
    2.  Initialize `maxDist = -1` and `seat = -1` to track the best option found.
    3.  **Check the first gap (from seat 0 to the first student):** The potential seat is `0`. The distance is `seats.get(0)`. If this distance is greater than `maxDist`, update `maxDist` to this distance and `seat` to `0`.
    4.  **Check internal gaps (between adjacent students):** Iterate through the `seats` list from the first to the second-to-last student. For each pair of adjacent students at `p1` and `p2`, calculate the midpoint `(p1 + p2) / 2`. The distance is `(p2 - p1) / 2`. If this distance is greater than `maxDist`, update `maxDist` and set `seat` to the midpoint.
    5.  **Check the last gap (from the last student to seat n-1):** The potential seat is `n-1`. The distance is `(n - 1) - seats.get(seats.size() - 1)`. If this distance is greater than `maxDist`, update `maxDist` and set `seat` to `n-1`.
    6.  After checking all gaps, `seat` holds the best position. Insert this `seat` into the `seats` list while maintaining its sorted order. A simple way is to add it and then call `Collections.sort()`.
    7.  Return the chosen `seat`.

*   **`leave(p)` method**:
    1.  Remove the integer `p` from the `seats` list. This requires finding the element and shifting subsequent elements.

## Using a Balanced Binary Search Tree (TreeSet)
This approach improves upon the `ArrayList` solution by using a `TreeSet`. A `TreeSet` is a balanced binary search tree that keeps elements sorted automatically and provides logarithmic time complexity for insertions and deletions. This significantly speeds up the `leave` operation.
**Time:** *   `seat()`: O(k). The iteration to find the best gap takes O(k) time, which dominates the O(log k) insertion time.
*   `leave(p)`: O(log k). Removing an element from a `TreeSet` is a logarithmic operation. · **Space:** O(k), where k is the number of occupied seats. The `TreeSet` stores one entry per student.
**Pros:** The `leave(p)` operation is very efficient, with a time complexity of O(log k).; The `seat()` operation benefits from a fast O(log k) insertion, although the overall complexity is still linear.; Maintains a clean, sorted representation of students without manual sorting.
**Cons:** The `seat()` operation remains the bottleneck. Although adding the new seat is fast (O(log k)), finding where to place it still requires iterating through all existing students, resulting in an O(k) time complexity.
### Explanation
By replacing the `ArrayList` with a `TreeSet`, we gain efficiency for operations that benefit from a sorted, tree-based structure.

### `seat()` operation:
The algorithm to find the best seat remains the same. We still need to check every gap between adjacent students to find the largest one. A `TreeSet` allows us to get the first (`seats.first()`) and last (`seats.last()`) students in O(log k) time, but iterating through all adjacent pairs still takes O(k) time. However, once the best seat is determined, adding it to the `TreeSet` is an efficient O(log k) operation, as the tree automatically rebalances itself.

### `leave()` operation:
This is where the `TreeSet` shines. Removing a student at seat `p` is a standard tree deletion operation, which takes O(log k) time. This is a major improvement over the O(k) time required for an `ArrayList`.

While `seat()` is still linear, the overall performance is better due to the much faster `leave()` calls.

```java
import java.util.TreeSet;

class ExamRoom {
    private TreeSet<Integer> seats;
    private int n;

    public ExamRoom(int n) {
        this.n = n;
        this.seats = new TreeSet<>();
    }
    
    public int seat() {
        if (seats.isEmpty()) {
            seats.add(0);
            return 0;
        }

        int maxDist = seats.first();
        int seat = 0;
        Integer prev = null;

        for (Integer current : seats) {
            if (prev != null) {
                int dist = (current - prev) / 2;
                if (dist > maxDist) {
                    maxDist = dist;
                    seat = prev + dist;
                }
            }
            prev = current;
        }

        if (n - 1 - seats.last() > maxDist) {
            seat = n - 1;
        }

        seats.add(seat);
        return seat;
    }
    
    public void leave(int p) {
        seats.remove(p);
    }
}
```
### Algorithm
*   **Constructor `ExamRoom(n)`**:
    1.  Initialize a `TreeSet<Integer>` called `seats`.
    2.  Store the total number of seats `n`.

*   **`seat()` method**:
    1.  If `seats` is empty, add `0` to `seats` and return `0`.
    2.  The logic for finding the best seat is identical to the `ArrayList` approach. We check the gap at the start, the gaps in the middle, and the gap at the end.
    3.  **Start gap:** Distance is `seats.first()`, seat is `0`.
    4.  **Middle gaps:** Iterate through the `TreeSet`. For each adjacent pair of seats `p1` and `p2`, the distance is `(p2 - p1) / 2` and the seat is `p1 + (p2 - p1) / 2`.
    5.  **End gap:** Distance is `n - 1 - seats.last()`, seat is `n-1`.
    6.  Keep track of the maximum distance and the corresponding seat with the lowest index.
    7.  After finding the best `seat`, add it to the `TreeSet` using `seats.add(seat)`.
    8.  Return the `seat`.

*   **`leave(p)` method**:
    1.  Call `seats.remove(p)` to remove the student from the `TreeSet`.

## Optimized Logarithmic Approach with TreeSet and Priority Queue
This is the most optimal solution, achieving logarithmic time complexity for both `seat` and `leave` operations. It cleverly combines a `TreeSet` to keep track of occupied seats with a `PriorityQueue` (acting as a max-heap) to efficiently find the largest available gap at any time.
**Time:** *   `seat()`: O(log k) amortized. Polling the `PriorityQueue` is O(log k). While there's a loop for lazy deletion, the total work is amortized over all operations. Adding to the `TreeSet` and `PriorityQueue` are also O(log k).
*   `leave(p)`: O(log k). Finding neighbors in the `TreeSet` is O(log k), removing from it is O(log k), and adding the new merged gap to the `PriorityQueue` is O(log k). · **Space:** O(k), where k is the number of occupied seats. We store each student in the `TreeSet` and each gap in the `PriorityQueue`.
**Pros:** Optimal time complexity: Both `seat()` and `leave()` operations run in O(log k) time (amortized for `seat`).; Highly scalable for a large number of calls to `seat` and `leave`.
**Cons:** This approach is significantly more complex to implement correctly.; The logic for the priority queue's comparator must carefully handle the different distance calculations for edge gaps vs. internal gaps and the tie-breaking rule.; Managing stale entries in the priority queue (lazy deletion) adds another layer of complexity to the `seat()` method.
### Explanation
The bottleneck in the previous approach was the linear scan to find the best gap. We can eliminate this scan by using a `PriorityQueue` to maintain the gaps, ordered by their potential to place a student with the maximum distance.

### Data Structures
*   **`TreeSet<Integer> seats`**: As before, this stores the sorted positions of students. Its key role here is to quickly find the neighbors of a student who is leaving, using `lower()` and `higher()` in O(log k) time.
*   **`PriorityQueue<int[]> pq`**: This max-heap stores all the available gaps, represented as `[start_seat, end_seat]`. A custom comparator ensures that the gap at the top of the heap is always the one that provides the best possible seat placement (i.e., maximizes the distance to the nearest person, with ties broken by lower seat index).

### `seat()` Operation
Instead of scanning, we simply ask the `PriorityQueue` for the best gap, which is an O(log k) operation. We take that gap, place the new student `p`, add `p` to our `TreeSet`, and then add the two new, smaller gaps created by the placement (`[start, p]` and `[p, end]`) back into the `PriorityQueue`.

### `leave()` Operation and Lazy Deletion
When a student at `p` leaves, we use the `TreeSet` to find their neighbors, `prev` and `next`. This tells us that the two gaps `[prev, p]` and `[p, next]` are now gone, and a new, larger gap `[prev, next]` has been created. We add this new gap to the `PriorityQueue`. The crucial insight is that we don't need to remove the old, now-invalid gaps from the `PriorityQueue`. This is called **lazy deletion**. We simply leave them there. When the `seat()` method polls a gap from the queue, it performs a quick check to see if it's still valid (by checking if the start and end points are still adjacent in the `TreeSet`). If not, it discards the stale gap and polls the next one. This makes both `seat()` and `leave()` operations efficient.

```java
import java.util.PriorityQueue;
import java.util.TreeSet;

class ExamRoom {
    private int n;
    private TreeSet<Integer> seats;
    private PriorityQueue<int[]> pq;

    public ExamRoom(int n) {
        this.n = n;
        this.seats = new TreeSet<>();
        // The PQ stores intervals [start, end].
        // The comparator prioritizes the interval with the largest distance.
        // Distance for [x, y] is (y - x) / 2.
        // For edge cases [0, x] or [y, n-1], the distance is x or n-1-y.
        // Tie is broken by the smaller start index.
        this.pq = new PriorityQueue<>((a, b) -> {
            int distA = getDistance(a);
            int distB = getDistance(b);
            if (distA != distB) {
                return distB - distA; // Max-heap
            }
            return a[0] - b[0]; // Smaller start index
        });
        pq.offer(new int[]{-1, n}); // Initial gap for the whole room
    }

    public int seat() {
        int seat = 0;
        int[] bestGap = pq.poll();

        // Lazy deletion: keep polling until we find a valid gap
        while (seats.contains(bestGap[0]) || seats.contains(bestGap[1]) || 
               (bestGap[0] != -1 && seats.higher(bestGap[0]) != null && seats.higher(bestGap[0]) != bestGap[1]) ||
               (bestGap[1] != n && seats.lower(bestGap[1]) != null && seats.lower(bestGap[1]) != bestGap[0])) {
            if(bestGap[0] != -1 && !seats.contains(bestGap[0])){
                 Integer higher = seats.higher(bestGap[0]);
                 if(higher != null) pq.offer(new int[]{bestGap[0], higher});
            }
            if(bestGap[1] != n && !seats.contains(bestGap[1])){
                 Integer lower = seats.lower(bestGap[1]);
                 if(lower != null) pq.offer(new int[]{lower, bestGap[1]});
            }
            bestGap = pq.poll();
        }

        if (bestGap[0] == -1) {
            seat = 0;
        } else if (bestGap[1] == n) {
            seat = n - 1;
        } else {
            seat = bestGap[0] + (bestGap[1] - bestGap[0]) / 2;
        }

        seats.add(seat);
        pq.offer(new int[]{bestGap[0], seat});
        pq.offer(new int[]{seat, bestGap[1]});

        return seat;
    }

    public void leave(int p) {
        Integer prev = seats.lower(p);
        Integer next = seats.higher(p);
        seats.remove(p);
        if (prev == null) prev = -1;
        if (next == null) next = n;
        pq.offer(new int[]{prev, next});
    }

    private int getDistance(int[] interval) {
        if (interval[0] == -1) {
            return interval[1];
        }
        if (interval[1] == n) {
            return n - 1 - interval[0];
        }
        return (interval[1] - interval[0]) / 2;
    }
}
```
*Note: The lazy deletion logic in the provided snippet is complex and may need refinement for all edge cases. It serves to illustrate the concept.*
### Algorithm
*   **Data Structures**:
    1.  `TreeSet<Integer> seats`: To store occupied seats and efficiently find neighbors (`lower`, `higher`).
    2.  `PriorityQueue<int[]> pq`: A max-heap to store available gaps `[start, end]` and quickly retrieve the best one.

*   **Comparator for `pq`**:
    1.  The `PriorityQueue` is ordered by a custom comparator.
    2.  For a gap `[start, end]`, calculate its effective distance. This is `end - start` for edge gaps (where `start` is 0 or `end` is `n-1`) and `(end - start) / 2` for internal gaps.
    3.  The comparator prioritizes the gap with the largest distance. Ties are broken by the smaller seat index.

*   **`seat()` method**:
    1.  Poll the `pq` to get the best available gap `[start, end]`.
    2.  This gap might be stale (invalidated by a previous `leave` or `seat` operation). We must loop, polling from the `pq`, until we find a valid gap. A gap `[s, e]` is valid if `seats.higher(s)` equals `e` (with special logic for boundaries).
    3.  Once a valid gap is found, calculate the new seat `p`.
    4.  Add `p` to the `seats` `TreeSet`.
    5.  The old gap `[start, end]` is now split. Add the two new gaps, `[start, p]` and `[p, end]`, back into the `pq`.

*   **`leave(p)` method**:
    1.  Use the `seats` `TreeSet` to find the neighbors of `p`: `prev = seats.lower(p)` and `next = seats.higher(p)`.
    2.  Remove `p` from `seats`.
    3.  The two gaps adjacent to `p`, `[prev, p]` and `[p, next]`, are now obsolete. They are merged into a new, larger gap `[prev, next]`.
    4.  Add this new merged gap `[prev, next]` to the `pq`. The old, smaller gaps are not explicitly removed (lazy deletion); they will be discarded as stale when polled by the `seat()` method.

# Solutions
### Java

```java
class ExamRoom { private TreeSet < int []> ts = new TreeSet <>(( a , b ) -> { int d1 = dist ( a ), d2 = dist ( b ); return d1 == d2 ? a [ 0 ] - b [ 0 ] : d2 - d1 ; }); private Map < Integer , Integer > left = new HashMap <>(); private Map < Integer , Integer > right = new HashMap <>(); private int n ; public ExamRoom ( int n ) { this . n = n ; add ( new int [] {- 1 , n }); } public int seat () { int [] s = ts . first (); int p = ( s [ 0 ] + s [ 1 ]) >> 1 ; if ( s [ 0 ] == - 1 ) { p = 0 ; } else if ( s [ 1 ] == n ) { p = n - 1 ; } del ( s ); add ( new int [] { s [ 0 ], p }); add ( new int [] { p , s [ 1 ]}); return p ; } public void leave ( int p ) { int l = left . get ( p ), r = right . get ( p ); del ( new int [] { l , p }); del ( new int [] { p , r }); add ( new int [] { l , r }); } private int dist ( int [] s ) { int l = s [ 0 ], r = s [ 1 ]; return l == - 1 || r == n ? r - l - 1 : ( r - l ) >> 1 ; } private void add ( int [] s ) { ts . add ( s ); left . put ( s [ 1 ], s [ 0 ]); right . put ( s [ 0 ], s [ 1 ]); } private void del ( int [] s ) { ts . remove ( s ); left . remove ( s [ 1 ]); right . remove ( s [ 0 ]); } } /** * Your ExamRoom object will be instantiated and called as such: * ExamRoom obj = new ExamRoom(n); * int param_1 = obj.seat(); * obj.leave(p); */
```

### CPP

```cpp
int N ; int dist ( const pair < int , int >& p ) { auto [ l , r ] = p ; if ( l == - 1 || r == N ) return r - l - 1 ; return ( r - l ) >> 1 ; } struct cmp { bool operator ()( const pair < int , int >& a , const pair < int , int >& b ) const { int d1 = dist ( a ), d2 = dist ( b ); return d1 == d2 ? a . first < b . first : d1 > d2 ; }; }; class ExamRoom { public: ExamRoom ( int n ) { N = n ; this -> n = n ; add ({ - 1 , n }); } int seat () { auto s = * ts . begin (); int p = ( s . first + s . second ) >> 1 ; if ( s . first == - 1 ) { p = 0 ; } else if ( s . second == n ) { p = n - 1 ; } del ( s ); add ({ s . first , p }); add ({ p , s . second }); return p ; } void leave ( int p ) { int l = left [ p ], r = right [ p ]; del ({ l , p }); del ({ p , r }); add ({ l , r }); } private: set < pair < int , int > , cmp > ts ; unordered_map < int , int > left ; unordered_map < int , int > right ; int n ; void add ( pair < int , int > s ) { ts . insert ( s ); left [ s . second ] = s . first ; right [ s . first ] = s . second ; } void del ( pair < int , int > s ) { ts . erase ( s ); left . erase ( s . second ); right . erase ( s . first ); } }; /** * Your ExamRoom object will be instantiated and called as such: * ExamRoom* obj = new ExamRoom(n); * int param_1 = obj->seat(); * obj->leave(p); */
```

### Python

```python
from sortedcontainers import SortedList class ExamRoom : def __init__ ( self , n : int ): def dist ( x ): l , r = x return r - l - 1 if l == - 1 or r == n else ( r - l ) >> 1 self . n = n self . ts = SortedList ( key = lambda x : ( - dist ( x ), x [ 0 ])) self . left = {} self . right = {} self . add (( - 1 , n )) def seat ( self ) -> int : s = self . ts [ 0 ] p = ( s [ 0 ] + s [ 1 ]) >> 1 if s [ 0 ] == - 1 : p = 0 elif s [ 1 ] == self . n : p = self . n - 1 self . delete ( s ) self . add (( s [ 0 ], p )) self . add (( p , s [ 1 ])) return p def leave ( self , p : int ) -> None : l , r = self . left [ p ], self . right [ p ] self . delete (( l , p )) self . delete (( p , r )) self . add (( l , r )) def add ( self , s ): self . ts . add ( s ) self . left [ s [ 1 ]] = s [ 0 ] self . right [ s [ 0 ]] = s [ 1 ] def delete ( self , s ): self . ts . remove ( s ) self . left . pop ( s [ 1 ]) self . right . pop ( s [ 0 ]) # Your ExamRoom object will be instantiated and called as such: # obj = ExamRoom(n) # param_1 = obj.seat() # obj.leave(p)
```