< Back





1845. Seat Reservation Manager

We're asked to create a seat reservation system. Given n, we create a pool of n seats numbered from
1 to n. If someone asks to reserve a seat, we return the minimum currently available seat - then
that seat is no longer available to reserve until it's unreserved. When unreserve is called with a
seat number, that seat is now available.

To easily solve this, we maintain a min heap and the current seat number, starting from 1. When
someone reserves a seat, if a seat is available in the heap, we return the minimum seat. Otherwise,
we increment the seat number and reserve it. When someone unreserves a seat, we add it back to the
heap.

The solution is as follows:


  from heapq import heapify, heappush, heappop

  class SeatManager:
      def __init__(self, n: int):
          self.h, self.curr = [], 1

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

          res, self.curr = self.curr, self.curr + 1
          return res

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


_ Time Complexity:

  O(m log(n)) - Unreserve is O(log(n)) and reserve and unreseve can be called m times.

_ Space Complexity:

  O(n) - The heap can store up to n seats in the worst case.