# LeetCode 855: Exam Room

## Problem Restatement

We need to design an `ExamRoom` class.

There are `n` seats in one row, labeled:

```python
0, 1, 2, ..., n - 1
```

When a student enters, they choose the seat that maximizes the distance to the closest occupied seat.

If several seats give the same distance, the student chooses the smallest seat number.

If the room is empty, the student sits at seat `0`.

We need to support two operations:

| Operation | Meaning |
|---|---|
| `seat()` | Choose a seat for the next student and return its index |
| `leave(p)` | Mark seat `p` as empty |

For `leave(p)`, the problem guarantees that a student is currently sitting at seat `p`.

## Input and Output

| Item | Meaning |
|---|---|
| Constructor input | `n`, the number of seats |
| `seat()` output | The chosen seat index |
| `leave(p)` output | Nothing |
| Main rule | Choose the seat farthest from the closest occupied seat |
| Tie rule | Choose the smallest seat index |

Class shape:

```python
class ExamRoom:

    def __init__(self, n: int):
        ...

    def seat(self) -> int:
        ...

    def leave(self, p: int) -> None:
        ...
```

## Examples

Example:

```python
examRoom = ExamRoom(10)

examRoom.seat()   # returns 0
examRoom.seat()   # returns 9
examRoom.seat()   # returns 4
examRoom.seat()   # returns 2
examRoom.leave(4)
examRoom.seat()   # returns 5
```

Walk through it.

At first, the room is empty, so the first student sits at `0`.

Occupied seats:

```python
[0]
```

The next student wants to be farthest from seat `0`, so they sit at `9`.

Occupied seats:

```python
[0, 9]
```

The next student sits in the middle, at `4`.

Occupied seats:

```python
[0, 4, 9]
```

The next student compares the gaps:

| Gap | Best seat | Distance to closest student |
|---|---|---|
| Between `0` and `4` | `2` | `2` |
| Between `4` and `9` | `6` | `2` |

Both give distance `2`, so choose the smaller seat index, `2`.

Occupied seats:

```python
[0, 2, 4, 9]
```

Then seat `4` leaves.

Occupied seats:

```python
[0, 2, 9]
```

The best open seat is now `5`, between `2` and `9`.

So the next `seat()` returns:

```python
5
```

## First Thought: Track Occupied Seats

The main thing we need to know is where students are currently sitting.

If we keep the occupied seats in sorted order, then every possible best seat comes from one of three places:

1. Seat `0`, before the first occupied seat
2. A midpoint between two adjacent occupied seats
3. Seat `n - 1`, after the last occupied seat

So for each `seat()` call, we can scan the sorted occupied seats and compute the best candidate.

This is simple and reliable.

In Python, we can store occupied seats in a sorted list and use `bisect.insort` to insert new seats while keeping the list sorted.

## Key Insight

Suppose two adjacent occupied seats are:

```python
left
right
```

The best seat between them is the midpoint:

```python
(left + right) // 2
```

The distance to the closest occupied seat is:

```python
(right - left) // 2
```

For the left edge, before the first occupied seat, the best candidate is seat `0`.

Its distance is:

```python
first_occupied - 0
```

For the right edge, after the last occupied seat, the best candidate is seat `n - 1`.

Its distance is:

```python
(n - 1) - last_occupied
```

We choose the candidate with the largest distance.

If distances tie, we keep the smaller seat index.

Scanning from left to right helps with ties, because smaller candidates appear earlier.

## Algorithm

Maintain:

```python
self.students
```

as a sorted list of occupied seats.

For `seat()`:

1. If no seats are occupied:
   1. Insert `0`
   2. Return `0`
2. Start with candidate seat `0`.
3. Its distance is the distance to the first occupied seat.
4. For every adjacent pair of occupied seats:
   1. Compute the midpoint.
   2. Compute its distance to the closest occupied seat.
   3. If this distance is larger than the current best, update the answer.
5. Check seat `n - 1`.
6. Insert the chosen seat into the sorted list.
7. Return it.

For `leave(p)`:

1. Remove `p` from the sorted list.

## Correctness

When the room is empty, the rule says the student must sit at seat `0`, and the algorithm does exactly that.

Now suppose the room is not empty.

Any empty seat belongs to one of three regions: before the first occupied seat, between two adjacent occupied seats, or after the last occupied seat.

In the left region, seat `0` is farthest from the first occupied seat, so it is the best candidate for that region.

In the right region, seat `n - 1` is farthest from the last occupied seat, so it is the best candidate for that region.

Between two adjacent occupied seats `left` and `right`, the seat that maximizes the minimum distance to both sides is the midpoint `(left + right) // 2`. If there are two central choices, the smaller index is correct because ties must choose the smaller seat.

Therefore, checking these candidates covers the best possible seat in every region.

The algorithm chooses the candidate with the largest distance. It only updates when it finds a strictly larger distance, so when distances tie, the earlier smaller candidate remains selected.

Thus, `seat()` always returns the seat required by the problem.

The `leave(p)` operation removes an occupied seat. Since the problem guarantees `p` is occupied, removing it restores the correct occupied-seat set.

## Complexity

Let `k` be the number of currently occupied seats.

| Operation | Time | Why |
|---|---|---|
| `seat()` | `O(k)` scan plus `O(k)` insertion | We scan occupied seats and insert into a sorted list |
| `leave(p)` | `O(k)` | Removing from a Python list may shift elements |
| Space | `O(k)` | We store occupied seats |

For the LeetCode constraints, this sorted-list approach is accepted and much simpler than an interval tree.

## Implementation

```python
from bisect import insort

class ExamRoom:

    def __init__(self, n: int):
        self.n = n
        self.students = []

    def seat(self) -> int:
        if not self.students:
            self.students.append(0)
            return 0

        best_seat = 0
        best_dist = self.students[0]

        for i in range(1, len(self.students)):
            left = self.students[i - 1]
            right = self.students[i]

            seat = (left + right) // 2
            dist = min(seat - left, right - seat)

            if dist > best_dist:
                best_dist = dist
                best_seat = seat

        last_seat = self.n - 1
        right_dist = last_seat - self.students[-1]

        if right_dist > best_dist:
            best_seat = last_seat

        insort(self.students, best_seat)
        return best_seat

    def leave(self, p: int) -> None:
        self.students.remove(p)
```

## Code Explanation

The constructor stores the number of seats and starts with no occupied seats:

```python
def __init__(self, n: int):
    self.n = n
    self.students = []
```

When the first student enters, the room is empty:

```python
if not self.students:
    self.students.append(0)
    return 0
```

The first candidate is seat `0`:

```python
best_seat = 0
best_dist = self.students[0]
```

If the first occupied seat is at index `7`, then seat `0` has distance `7`.

Next, we inspect every gap between adjacent occupied seats:

```python
for i in range(1, len(self.students)):
    left = self.students[i - 1]
    right = self.students[i]
```

The best seat in this gap is the midpoint:

```python
seat = (left + right) // 2
```

Its distance to the closest occupied seat is:

```python
dist = min(seat - left, right - seat)
```

If this distance is better than the best one found so far, we update:

```python
if dist > best_dist:
    best_dist = dist
    best_seat = seat
```

We use `>` rather than `>=`.

That preserves the smaller seat index in a tie.

After checking middle gaps, we check the right edge:

```python
last_seat = self.n - 1
right_dist = last_seat - self.students[-1]
```

If the right edge gives a strictly better distance, choose it:

```python
if right_dist > best_dist:
    best_seat = last_seat
```

Finally, insert the selected seat while keeping the list sorted:

```python
insort(self.students, best_seat)
```

For leaving:

```python
self.students.remove(p)
```

This removes the occupied seat `p`.

## Testing

```python
def test_exam_room():
    room = ExamRoom(10)

    assert room.seat() == 0
    assert room.seat() == 9
    assert room.seat() == 4
    assert room.seat() == 2
    room.leave(4)
    assert room.seat() == 5

    room = ExamRoom(5)
    assert room.seat() == 0
    assert room.seat() == 4
    assert room.seat() == 2
    assert room.seat() == 1
    assert room.seat() == 3

    room.leave(0)
    assert room.seat() == 0

    room = ExamRoom(3)
    assert room.seat() == 0
    assert room.seat() == 2
    room.leave(0)
    assert room.seat() == 0

    print("all tests passed")

test_exam_room()
```

Test meaning:

| Test | Why |
|---|---|
| Official-style sequence | Checks seat selection and `leave` |
| Fill all seats | Checks repeated midpoint and tie behavior |
| Leave first seat | Checks left edge candidate |
| Small room | Checks boundary behavior |