Seat Reservation Manager

How it works

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.

Steps

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.

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)

Things to watch for

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.

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)

class SeatManager {
private:
    set<int> available;
    int nextSeat;

public:
    SeatManager(int n) {
        nextSeat = 1;
    }

    int reserve() {
        if (!available.empty()) {
            int seat = *available.begin();
            available.erase(available.begin());
            return seat;
        }
        return nextSeat++;
    }

    void unreserve(int seatNumber) {
        available.insert(seatNumber);
    }
};