> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Exam Room Python Solution with Tests

> Tested Python solution for LeetCode 855 with 22 pytest cases. Generate a practice environment with lcpy.

LeetCode 855, [Medium](/catalog/medium). Topics: [Design](/catalog/topics/design), [Heap (Priority Queue)](/catalog/topics/heap-priority-queue), [Ordered Set](/catalog/topics/ordered-set). [View on LeetCode](https://leetcode.com/problems/exam-room/description/).

Generate this problem as a practice environment: tested reference solution, 22 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 855   # by problem number
lcpy gen -s exam_room   # by problem name
```

## 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 sit.
* `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`.

### Examples

```
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 <= 10^9`
* It is guaranteed that there is a student sitting at seat `p`.
* At most `10^4` calls will be made to `seat` and `leave`.

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/exam_room/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/exam_room/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
import heapq
from bisect import bisect_left, insort


class ExamRoom:
    # Time: __init__ O(1), seat O(log k) amortized, leave O(log k + k)
    # Space: O(k) for k occupied seats

    def __init__(self, n: int) -> None:
        self.n = n
        self.occupied: list[int] = []
        self.gaps: list[tuple[int, int, int]] = []
        self._push(-1, n)

    def _push(self, left: int, right: int) -> None:
        if right - left < 2:
            return
        if left == -1:
            dist = right
        elif right == self.n:
            dist = self.n - 1 - left
        else:
            dist = (right - left) // 2
        heapq.heappush(self.gaps, (-dist, left, right))

    def _valid(self, left: int, right: int) -> bool:
        occ = self.occupied
        if left == -1:
            return (right == self.n) if not occ else occ[0] == right
        if right == self.n:
            return occ[-1] == left
        i = bisect_left(occ, left)
        return i + 1 < len(occ) and occ[i] == left and occ[i + 1] == right

    def seat(self) -> int:
        while True:
            _, left, right = heapq.heappop(self.gaps)
            if not self._valid(left, right):
                continue
            if left == -1:
                pos = 0
            elif right == self.n:
                pos = self.n - 1
            else:
                pos = (left + right) // 2
            insort(self.occupied, pos)
            self._push(left, pos)
            self._push(pos, right)
            return pos

    def leave(self, p: int) -> None:
        self.occupied.remove(p)
        i = bisect_left(self.occupied, p)
        left = self.occupied[i - 1] if i > 0 else -1
        right = self.occupied[i] if i < len(self.occupied) else self.n
        self._push(left, right)
```

## Complexity

| Time | Space |
| - | - |
| **init** O(1), seat O(log k) amortized, leave O(log k + k) | O(k) for k occupied seats |

## Tags


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.