> ## 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.

# Seat Reservation Manager Python Solution

> Tested Python solution for LeetCode 1845 with 15 pytest cases. Generate a practice environment with lcpy.

LeetCode 1845, [Medium](/catalog/medium). Topics: [Design](/catalog/topics/design), [Heap (Priority Queue)](/catalog/topics/heap-priority-queue). [View on LeetCode](https://leetcode.com/problems/seat-reservation-manager/description/).

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

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

## Problem

Design a system that manages the reservation state of `n` seats that are numbered from `1` to `n`.

Implement the `SeatManager` class:

* `SeatManager(int n)` Initializes a `SeatManager` object that will manage `n` seats numbered from `1` to `n`. All seats are initially available.
* `int reserve()` Fetches the **smallest-numbered** unreserved seat, reserves it, and returns its number.
* `void unreserve(int seatNumber)` Unreserves the seat with the given `seatNumber`.

### Examples

```
Input
["SeatManager", "reserve", "reserve", "unreserve", "reserve", "reserve", "reserve", "reserve", "unreserve"]
[[5], [], [], [2], [], [], [], [], [5]]
Output
[null, 1, 2, null, 2, 3, 4, 5, null]

Explanation
SeatManager seatManager = new SeatManager(5); // Initializes a SeatManager with 5 seats.
seatManager.reserve();    // All seats are available, so return the lowest numbered seat, which is 1.
seatManager.reserve();    // The available seats are [2,3,4,5], so return the lowest of them, which is 2.
seatManager.unreserve(2); // Unreserve seat 2, so now the available seats are [2,3,4,5].
seatManager.reserve();    // The available seats are [2,3,4,5], so return the lowest of them, which is 2.
seatManager.reserve();    // The available seats are [3,4,5], so return the lowest of them, which is 3.
seatManager.reserve();    // The available seats are [4,5], so return the lowest of them, which is 4.
seatManager.reserve();    // The only available seat is seat 5, so return 5.
seatManager.unreserve(5); // Unreserve seat 5, so now the available seats are [5].
```

### Constraints

* `1 <= n <= 10^5`
* `1 <= seatNumber <= n`
* For each call to `reserve`, it is guaranteed that there will be at least one unreserved seat.
* For each call to `unreserve`, it is guaranteed that `seatNumber` will be reserved.
* At most `10^5` calls in total will be made to `reserve` and `unreserve`.

## Solution

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

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
import heapq


class SeatManager:
    # Time: O(1) init, O(log n) reserve, O(log n) unreserve
    # Space: O(n)
    def __init__(self, n: int) -> None:
        self.next_seat = 1
        self.returned: list[int] = []

    def reserve(self) -> int:
        if self.returned and self.returned[0] < self.next_seat:
            return heapq.heappop(self.returned)
        seat = self.next_seat
        self.next_seat += 1
        return seat

    def unreserve(self, seat_number: int) -> None:
        heapq.heappush(self.returned, seat_number)
```

## Complexity

| Time | Space |
| - | - |
| O(1) init, O(log n) reserve, O(log n) unreserve | O(n) |

## Tags

[NeetCode All](/catalog/neetcode).


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