Seat reservation manager

September 6, 2022


Problem URL: Seat reservation manager

We will create a min heap with the capacity of the seat manager. Then when someone reserve a seat, we will pop it from our min heap, and when someone unreserve a seat, we will push back the value to our heap.

class SeatManager:
    def __init__(self, n: int):
        self.heap = [i for i in range(1, n+1)]

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

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

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

Time Complexity: O(n) for init, O(1) for rest of the operations
Space Complexity: O(n)