#1845

Medium

auto_awesomeDesign plus Heap (Priority Queue)

LeetCode Problem Workspace

Seat Reservation Manager

Manage seat reservations efficiently using a design combining priority queue to always return the lowest available seat quickly.

design heap priority queue

Problem Statement

Design a system to manage seat reservations for n seats numbered from 1 to n. Implement the SeatManager class to handle reservation and unreservation efficiently using a structure that returns the smallest available seat first.

SeatManager must support reserve and unreserve operations. Reserve should return the lowest-numbered unreserved seat, and unreserve should free a specific seat for future reservations. Your design should handle up to 10^5 seats and operations efficiently.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

Input ["SeatManager", "reserve", "reserve", "unreserve", "reserve", "reserve", "reserve", "reserve", "unreserve"] [[5], [], [], [2], [], [], [], [], [5]] Output [null, 1, 2, null, 2, 3, 4, 5, null]

Explanation SeatManager seatManager = new SeatManager(5); // Initializes a SeatManager with 5 seats. seatManager.reserve(); // All seats are available, so return the lowest numbered seat, which is 1. seatManager.reserve(); // The available seats are [2,3,4,5], so return the lowest of them, which is 2. seatManager.unreserve(2); // Unreserve seat 2, so now the available seats are [2,3,4,5]. seatManager.reserve(); // The available seats are [2,3,4,5], so return the lowest of them, which is 2. seatManager.reserve(); // The available seats are [3,4,5], so return the lowest of them, which is 3. seatManager.reserve(); // The available seats are [4,5], so return the lowest of them, which is 4. seatManager.reserve(); // The only available seat is seat 5, so return 5. seatManager.unreserve(5); // Unreserve seat 5, so now the available seats are [5].

Constraints

1 <= n <= 105
1 <= seatNumber <= n
For each call to reserve, it is guaranteed that there will be at least one unreserved seat.
For each call to unreserve, it is guaranteed that seatNumber will be reserved.
At most 105 calls in total will be made to reserve and unreserve.

Solution Approach

Use a Min-Heap for Available Seats

Initialize a min-heap containing all seat numbers. Each reserve operation pops the smallest seat from the heap, ensuring O(log n) access to the lowest available seat. Unreserve operations push the freed seat back into the heap, maintaining heap order automatically.

Track Seat States

Optionally maintain an array to track reserved seats, allowing validation of unreserve calls. This ensures no unreserved seat is released twice and avoids heap inconsistencies during operations.

Handle Large n Efficiently

Since n and operation count can be up to 10^5, avoid linear searches. Heap operations provide logarithmic complexity, making the solution scalable. Initialize the heap once and rely on its properties for both reserve and unreserve to maintain efficiency.

Complexity Analysis

Metric	Value
Time	O(m \cdot \log n)
Space	O(n)

Each reserve and unreserve operation runs in O(log n) due to heap operations. Space complexity is O(n) for the heap storing all available seats.

What Interviewers Usually Probe

Are you using a data structure that always gives the smallest available seat?
Can your design handle up to 10^5 seats efficiently without linear scans?
How do you ensure unreserve operations maintain heap consistency?

Common Pitfalls or Variants

Common pitfalls

Using a simple array scan for reserve leads to O(n) per operation and times out on large n.
Not pushing unreserved seats back into the heap correctly can break the ordering guarantee.
Ignoring seat state validation may allow unreserve on an already unreserved seat.

Follow-up variants

Track multiple classes of seats (premium, regular) using separate heaps.
Implement the same SeatManager but with random seat assignment instead of lowest-numbered.
Extend to support batch reserve or unreserve operations efficiently.

FAQ

What is the main pattern behind Seat Reservation Manager?

It combines design with a min-heap priority queue to always retrieve the lowest-numbered available seat efficiently.

Can I use a simple array instead of a heap?

Using an array leads to O(n) reserve operations, which is too slow for large n. A heap maintains O(log n) efficiency.

How do I handle unreserve calls safely?

Push the unreserved seat back into the heap and optionally mark it in a tracking array to prevent duplicates.

What is the time complexity per operation?

Each reserve or unreserve operation runs in O(log n) due to heap insertion and removal.

Can this approach handle the maximum constraints?

Yes, the min-heap approach efficiently manages up to 10^5 seats and 10^5 operations without performance issues.

terminal

Solution

Solution 1: Priority Queue (Min-Heap)

We define a priority queue (min-heap) $\textit{q}$ to store all the available seat numbers. Initially, we add all seat numbers from $1$ to $n$ into $\textit{q}$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

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

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

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


# Your SeatManager object will be instantiated and called as such:
# obj = SeatManager(n)
# param_1 = obj.reserve()
# obj.unreserve(seatNumber)

Continue Practicing

#1825 finding mk average #1912 design movie rental system #2034 stock price fluctuation