Seat Manager Design

Design a SeatManager class that assigns seats in increasing order and supports unreserving.

heap class-design simulation greedy

Design a class `SeatManager` that handles seat reservations in an airplane with `n` seats numbered from 1 to `n`. Initially, all seats are available.

Your task is to implement the following methods:

- `__init__(self, n: int)` — Initializes the manager with `n` seats. All seats are initially available.
- `reserve(self) -> int` — Fetches the smallest-numbered unreserved seat, reserves it, and returns its number.
- `unreserve(self, seat_number: int) -> None` — Unreserves the given seat, making it available again.

You can assume that all calls to `reserve` are valid: there is always at least one unreserved seat when `reserve` is called. Also, `unreserve` will only be called with a seat that is currently reserved.

Additionally, the test harness calls the function `seat_manager_operations(n, operations)` that simulates a sequence of operations on the class. The operations are given as a list where each operation is either the string `"reserve"` or the string `"unreserve"` followed by the seat number as the next element (so `["reserve", "unreserve", 2, "reserve"]` means reserve, unreserve seat 2, reserve). This function must return a list representing the results: for `"reserve"` append the returned seat number; for `"unreserve"` append `None`. Implement both the class and the function.

Constraints

1 ≤ n ≤ 10^5
At most 10^5 calls will be made to `reserve` and `unreserve` in total.
Each `seat_number` in `unreserve` will be a valid reserved seat.
The solution should have O(log n) time per operation and O(n) space, or better.

Example

>>> manager = SeatManager(5)
>>> manager.reserve()
1
>>> manager.reserve()
2
>>> manager.unreserve(2)
>>> manager.reserve()
2
>>> manager.reserve()
3
>>> manager.reserve()
4
>>> manager.reserve()
5
>>> manager.reserve()
1
>>> seat_manager_operations(5, ["reserve", "reserve", "unreserve", 2, "reserve"])
[1, 2, None]

25 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Use a min-heap (heapq) to always pop the smallest available seat number.

In `__init__`, push all seat numbers 1 through n into a heap.

In `reserve`, pop from the heap; in `unreserve`, push the seat back.

For `seat_manager_operations`, iterate through the operations list and when encountering the string "unreserve", the next element is the seat number.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.