Problem Description

You need to design a seat reservation system that manages n seats numbered from 1 to n.

The system should support the following operations through a SeatManager class:

1. Constructor SeatManager(int n): Initialize the system with n seats (numbered 1 through n). All seats start as available/unreserved.

2. Method reserve(): Find and reserve the smallest-numbered seat that is currently unreserved. Return the seat number that was reserved.

3. Method unreserve(int seatNumber): Make the specified seat number available again (unreserve it).

The key requirement is that when reserving a seat, you must always select the smallest-numbered unreserved seat available.

For example, if seats 1, 3, and 5 are available, calling reserve() should reserve seat 1 and return 1. If someone then unreserves seat 2, the next call to reserve() would reserve seat 2 (not seat 3), since 2 is now the smallest available seat number.

The solution uses a min-heap (priority queue) to efficiently track and retrieve the smallest available seat number. Initially, all seat numbers from 1 to n are added to the heap. When reserve() is called, the smallest element is popped from the heap. When unreserve(seatNumber) is called, that seat number is pushed back onto the heap to make it available again.

Intuition

The core challenge is efficiently finding the smallest unreserved seat number at any given time. Let's think through different approaches:

If we used a simple boolean array to track which seats are reserved, finding the smallest unreserved seat would require scanning through the array from the beginning each time, taking O(n) time for each reservation.

We need a data structure that can:

1. Give us the minimum value quickly
2. Allow us to remove that minimum value
3. Allow us to add values back when seats are unreserved

This naturally points us toward a min-heap (priority queue). A min-heap maintains its elements in a way where the smallest element is always at the root and can be accessed in O(1) time and removed in O(log n) time.

When we initialize the system, we have all seats from 1 to n available. We can add all these numbers to our min-heap.

When someone reserves a seat, we need the smallest available number - that's exactly what heappop() gives us by removing and returning the root of the min-heap.

When someone unreserves a seat, that seat number becomes available again. We simply add it back to our heap with heappush(), and the heap property ensures it will be positioned correctly among other available seats.

The beauty of this approach is that the heap automatically maintains the ordering for us. We don't need to sort or search - the heap structure guarantees that we can always get the minimum element efficiently.

Learn more about Heap (Priority Queue) patterns.

Solution Approach

The solution implements a seat reservation system using a min-heap (priority queue) to efficiently manage available seats.

Data Structure Choice

We use a min-heap stored in the variable self.q to maintain all available seat numbers. Python's heapq module provides heap operations on regular lists, where the smallest element is always at index 0.

Implementation Details

1. Initialization (__init__ method):

def __init__(self, n: int):
    self.q = list(range(1, n + 1))

• Create a list containing all seat numbers from 1 to n using range(1, n + 1)
• This list represents our initial heap with all seats available
• Since the list is already sorted in ascending order, it satisfies the min-heap property without needing heapification

2. Reserving a Seat (reserve method):

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

• Use heappop() to remove and return the smallest element from the heap
• This operation maintains the heap property after removal
• Time complexity: O(log n) where n is the number of available seats

3. Unreserving a Seat (unreserve method):

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

• Use heappush() to add the seat number back to the heap
• The heap automatically reorganizes to maintain the min-heap property
• Time complexity: O(log n) where n is the number of available seats

Why This Works

The min-heap guarantees that:

• The smallest available seat number is always at the root (index 0)
• Both insertion and extraction of the minimum maintain logarithmic time complexity
• No manual sorting or searching is required - the heap structure handles ordering automatically

Complexity Analysis

• Space Complexity: O(n) to store at most n seat numbers
• Time Complexity:
  • Initialization: O(n) to create the initial list
  • Reserve: O(log n) for heap pop operation
  • Unreserve: O(log n) for heap push operation

Example Walkthrough

Let's walk through a concrete example with a seat manager for 5 seats.

Initial Setup: SeatManager(5)

• We create a min-heap with seats [1, 2, 3, 4, 5]
• Heap visualization: [1, 2, 3, 4, 5] (smallest at front)

Operation 1: reserve()

• Call heappop() which removes and returns the smallest element (1)
• Heap after: [2, 3, 4, 5]
• Returns: 1 (seat 1 is now reserved)

Operation 2: reserve()

• Call heappop() which removes and returns the smallest element (2)
• Heap after: [3, 4, 5]
• Returns: 2 (seat 2 is now reserved)

Operation 3: unreserve(1)

• Call heappush(1) to add seat 1 back to available seats
• The heap reorganizes to maintain min-heap property
• Heap after: [1, 3, 4, 5] (notice 1 is back at the front)

Operation 4: reserve()

• Call heappop() which removes and returns the smallest element (1)
• Heap after: [3, 4, 5]
• Returns: 1 (seat 1 is reserved again - it was the smallest available)

Operation 5: unreserve(2)

• Call heappush(2) to add seat 2 back
• The heap reorganizes to place 2 in the correct position
• Heap after: [2, 3, 4, 5]

Operation 6: reserve()

• Call heappop() which removes and returns the smallest element (2)
• Heap after: [3, 4, 5]
• Returns: 2

This example demonstrates how the min-heap always maintains the smallest available seat at the root, making it efficient to find and reserve the lowest-numbered available seat. When seats are unreserved, they're automatically placed in the correct position within the heap structure.

Solution Implementation

Time and Space Complexity

Time Complexity:

• __init__(n): O(n) - Creating a list with elements from 1 to n takes linear time. Although the list is treated as a min-heap, Python's list initialization doesn't require heapification when elements are already in sorted order (1 to n is already a valid min-heap).

• reserve(): O(log n) - The heappop operation removes the minimum element from the heap and maintains the heap property, which requires O(log n) time due to the bubble-down process.

• unreserve(seatNumber): O(log n) - The heappush operation inserts an element into the heap and maintains the heap property through bubble-up, taking O(log n) time.

Space Complexity:

• O(n) - The heap stores up to n seat numbers in the worst case (when no seats are reserved), requiring linear space proportional to the number of seats.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Assuming Seats Start at Index 0

A common mistake is initializing the heap with seats numbered from 0 to n-1 instead of 1 to n.

Incorrect:

def __init__(self, n: int):
    self.available_seats = list(range(n))  # Creates [0, 1, 2, ..., n-1]

Correct:

def __init__(self, n: int):
    self.available_seats = list(range(1, n + 1))  # Creates [1, 2, 3, ..., n]

2. Not Handling Edge Cases in reserve()

Calling reserve() when no seats are available will cause a crash. While the problem may guarantee this won't happen, defensive programming is good practice.

Better Implementation:

def reserve(self) -> int:
    if not self.available_seats:
        return -1  # or raise an exception
    return heapq.heappop(self.available_seats)

3. Using heapify() Unnecessarily

Since range(1, n + 1) already produces a sorted list (which is a valid min-heap), calling heapq.heapify() is redundant and wastes O(n) time.

Unnecessary:

def __init__(self, n: int):
    self.available_seats = list(range(1, n + 1))
    heapq.heapify(self.available_seats)  # Not needed!

4. Using a Set Instead of a Heap

While a set can track available seats, finding the minimum requires O(n) time, making reserve() inefficient.

Inefficient Approach:

def __init__(self, n: int):
    self.available_seats = set(range(1, n + 1))

def reserve(self) -> int:
    seat = min(self.available_seats)  # O(n) operation!
    self.available_seats.remove(seat)
    return seat

5. Duplicate Unreserving

The current implementation doesn't prevent unreserving an already-available seat, which could lead to duplicate entries in the heap.

Robust Solution:

class SeatManager:
    def __init__(self, n: int):
        self.available_seats = list(range(1, n + 1))
        self.available_set = set(range(1, n + 1))  # Track available seats
  
    def reserve(self) -> int:
        seat = heapq.heappop(self.available_seats)
        self.available_set.remove(seat)
        return seat
  
    def unreserve(self, seatNumber: int) -> None:
        if seatNumber not in self.available_set:  # Prevent duplicates
            heapq.heappush(self.available_seats, seatNumber)
            self.available_set.add(seatNumber)