Seat Reservation Manager Python Solution

lcpy gen -n 1845   # by problem number
lcpy gen -s seat_reservation_manager   # by problem name

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

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)