Seat Reservation Manager — LeetCode 1845 Python Solution

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

Example

Input

["SeatManager", "reserve", "reserve", "unreserve", "reserve", "reserve", "reserve", "reserve", "unreserve"]

Output

[null, 1, 2, null, 2, 3, 4, 5, null]

Explanation

SeatManager seatManager = new SeatManager(5); // Initializes a SeatManager with 5 seats.

Python solution

class SeatManager:
    def __init__(self, n: int):
        self.q = list(range(1, n + 1))

    def reserve(self) -> int:
        return heappop(self.q)

    def unreserve(self, seatNumber: int) -> None:
        heappush(self.q, seatNumber)


# Your SeatManager object will be instantiated and called as such:
# obj = SeatManager(n)
# param_1 = obj.reserve()
# obj.unreserve(seatNumber)

Complexity

Pattern: Heap / Priority Queue

Keep only the best k elements, or always pull the smallest, in log time. LeetCode 1845. Seat Reservation Manager is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Heap (Priority Queue).

The heap / priority queue guide has the Python template for the pattern and the 163 LeetCode problems that use it.

Related problems