1845. Seat Reservation Manager - Explanation

Problem Link

1. Brute Force

Intuition

The simplest way to manage seat reservations is to track each seat's status with a boolean array. When someone reserves, we scan from the beginning to find the first unreserved seat. When someone unreserves, we simply mark that seat as available again. This guarantees we always return the smallest available seat number, but the linear scan makes reservations slow for large numbers of seats.

Algorithm

1. Initialize a boolean array seats of size n, where false means unreserved.
2. For reserve():
   • Scan through the array from index 0.
   • Find the first seat that is false (unreserved).
   • Mark it as true (reserved) and return the seat number (index + 1).
3. For unreserve(seatNumber):
   • Mark seats[seatNumber - 1] as false.

class SeatManager:

    def __init__(self, n: int):
        self.seats = [False] * n

    def reserve(self) -> int:
        for i in range(len(self.seats)):
            if not self.seats[i]:
                self.seats[i] = True
                return i + 1

    def unreserve(self, seatNumber: int) -> None:
        self.seats[seatNumber - 1] = False

Time & Space Complexity

• Time complexity:
  • $O(n)$ time for initialization.
  • $O(n)$ time for each $reserve()$ function call.
  • $O(1)$ time for each $unreserve()$ function call.
• Space complexity: $O(n)$

---

2. Min-Heap

Intuition

To efficiently retrieve the smallest available seat, we can use a min-heap. By initializing the heap with all seat numbers from 1 to n, the smallest seat is always at the top. Reserving pops from the heap, and unreserving pushes back onto it. The heap maintains the ordering automatically.

Algorithm

1. Initialize a min-heap with all seat numbers from 1 to n.
2. For reserve():
   • Pop and return the minimum element from the heap.
3. For unreserve(seatNumber):
   • Push seatNumber back into the heap.

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

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

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

Time & Space Complexity

• Time complexity:
  • $O(n \log n)$ time for initialization.
  • $O(\log n)$ time for each $reserve()$ function call.
  • $O(\log n)$ time for each $unreserve()$ function call.
• Space complexity: $O(n)$

---

3. Min-Heap (Optimal)

Intuition

Rather than pre-populating the heap with all n seats, we can lazily assign seats. We track a counter nextSeat that represents the next fresh seat to assign. When reserving, if no previously unreserved seats are in the heap, we simply hand out nextSeat and increment it. This avoids O(n log n) initialization and handles the common case where seats are reserved in order very efficiently.

Algorithm

1. Initialize an empty min-heap and set nextSeat = 1.
2. For reserve():
   • If the heap is not empty, pop and return the minimum.
   • Otherwise, return nextSeat and increment it.
3. For unreserve(seatNumber):
   • Push seatNumber into the heap.

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

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

        seat = self.nextSeat
        self.nextSeat += 1
        return seat

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

Time & Space Complexity

• Time complexity:
  • $O(1)$ time for initialization.
  • $O(\log n)$ time for each $reserve()$ function call.
  • $O(\log n)$ time for each $unreserve()$ function call.
• Space complexity: $O(n)$

---

4. Ordered Set

Intuition

An ordered set (like TreeSet or SortedSet) keeps elements sorted and allows efficient retrieval of the minimum. Similar to the optimal min-heap approach, we lazily track unreserved seats. The ordered set provides O(log n) insertion, deletion, and minimum retrieval, making it a clean alternative to the heap.

Algorithm

1. Initialize an empty ordered set available and set nextSeat = 1.
2. For reserve():
   • If the set is not empty, remove and return the smallest element.
   • Otherwise, return nextSeat and increment it.
3. For unreserve(seatNumber):
   • Add seatNumber to the set.

class SeatManager:
    def __init__(self, n: int):
        self.available = SortedSet()
        self.nextSeat = 1

    def reserve(self) -> int:
        if self.available:
            return self.available.pop(0)

        seat = self.nextSeat
        self.nextSeat += 1
        return seat

    def unreserve(self, seatNumber: int) -> None:
        self.available.add(seatNumber)

Time & Space Complexity

• Time complexity:
  • $O(1)$ time for initialization.
  • $O(\log n)$ time for each $reserve()$ function call.
  • $O(\log n)$ time for each $unreserve()$ function call.
• Space complexity: $O(n)$

---

Common Pitfalls

Pre-populating All Seats in the Heap

A common inefficiency is initializing the min-heap with all n seats upfront. This results in O(n log n) initialization time and O(n) space even when only a few reservations are made. The optimal approach uses lazy initialization: track a nextSeat counter and only add seats to the heap when they are unreserved.

Off-by-One Errors with 1-Based Seat Numbers

Seat numbers in this problem are 1-indexed, but arrays are 0-indexed. A frequent mistake is confusing these indexing schemes, leading to returning seat 0 (invalid) or accessing seats[seatNumber] instead of seats[seatNumber - 1] when using a boolean array approach.

Using a Max-Heap Instead of a Min-Heap

When implementing the heap-based solution, accidentally using a max-heap instead of a min-heap will return the largest available seat number instead of the smallest. Ensure you configure the heap correctly for minimum extraction, which may require using a custom comparator or negating values depending on your language.