1845. Seat Reservation Manager - Explanation

1. Brute Force

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

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)

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

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)$