{x}
blog image

Seat Reservation Manager

Design a system that manages the reservation state of n seats that are numbered from 1 to n.

Implement the SeatManager class:

  • SeatManager(int n) Initializes a SeatManager object that will manage n seats numbered from 1 to n. All seats are initially available.
  • int reserve() Fetches the smallest-numbered unreserved seat, reserves it, and returns its number.
  • void unreserve(int seatNumber) Unreserves the seat with the given seatNumber.

 

Example 1:

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 Explanation: Seat Reservation Manager

This problem requires designing a system to manage seat reservations. The optimal approach leverages a min-heap data structure (priority queue) to efficiently track available seats and provide fast reservation and unreservation operations.

Core Idea:

A min-heap keeps track of available seats, always presenting the smallest available seat number at its top. This allows for O(log n) time complexity for both reservation and unreservation, where n is the total number of seats.

Algorithm:

  1. Initialization (SeatManager(int n)): The constructor creates a min-heap and populates it with all seat numbers from 1 to n. This initial population takes O(n log n) time in the worst case (depending on the heap implementation; some allow for O(n) amortized insertion).

  2. Reservation (reserve()): The reserve method simply extracts (and removes) the minimum element (smallest available seat) from the min-heap using heappop (Python) or poll (Java, C++). This operation is O(log n).

  3. Unreservation (unreserve(int seatNumber)): The unreserve method adds the given seatNumber back into the min-heap using heappush (Python) or offer (Java, C++). This operation is also O(log n).

Time Complexity Analysis:

  • Constructor: O(n log n) (worst case, due to heap initialization). Some heap implementations offer O(n) amortized time for bulk insertion.
  • reserve(): O(log n)
  • unreserve(): O(log n)

Space Complexity Analysis:

  • O(n) to store the min-heap of available seats.

Code Examples (Python, Java, C++, Go, TypeScript, C#):

The provided code snippets showcase this approach across multiple languages. Each snippet follows the same fundamental structure:

  • A min-heap (priority queue) is used.
  • The constructor initializes the heap with all available seats.
  • reserve pops the smallest element.
  • unreserve inserts the given seat number back into the heap.

Note: The choice of using a min-heap is crucial for maintaining the efficiency of finding the smallest available seat quickly. Other approaches (like maintaining a sorted set or using a bit vector) could be less efficient, especially for a large number of seats and frequent operations. The min-heap provides the optimal balance between space and time complexity for this specific problem.