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.