Taro Logo

Seat Reservation Manager

Medium
Google logo
Google
1 view
Topics:
Greedy AlgorithmsArrays

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.

For example:

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 <= 10^5
  • 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 10^5 calls in total will be made to reserve and unreserve.

Solution


Seat Manager System Design

Problem Description

Design a system that manages the reservation state of n seats numbered from 1 to n. Implement the SeatManager class with the following functionalities:

  • SeatManager(int n): Initializes a SeatManager object that manages n seats. 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.

Naive Solution

A straightforward approach involves using a boolean array to track the availability of each seat. Initially, all seats are marked as available (true). The reserve() operation would iterate through the array to find the first available seat (smallest index with a true value), mark it as reserved (set to false), and return the seat number. The unreserve(int seatNumber) operation would simply set the corresponding index in the boolean array back to true.

Code (Python)

class SeatManager:
    def __init__(self, n: int):
        self.seats = [True] * n  # True means available

    def reserve(self) -> int:
        for i in range(len(self.seats)):
            if self.seats[i]:
                self.seats[i] = False
                return i + 1
        return -1  # Should not happen based on problem constraints

    def unreserve(self, seatNumber: int) -> None:
        self.seats[seatNumber - 1] = True

Time and Space Complexity

  • Time Complexity:
    • SeatManager(int n): O(n) to initialize the boolean array.
    • reserve(): O(n) in the worst case, as it may need to iterate through the entire array.
    • unreserve(int seatNumber): O(1).
  • Space Complexity: O(n) to store the boolean array representing seat availability.

Edge Cases

  • n = 1: A single seat exists. The naive method will work fine in this situation.
  • Many reserve() calls: The naive method will continue to work, but will get slower as more and more seats are reserved.
  • Many unreserve() calls: This can make subsequent reserve() calls faster, but on average, the time to reserve() will increase linearly with n as the algorithm iterates to find open seats.

Optimal Solution

A more efficient approach uses a min-heap (priority queue) to store the available seat numbers. Initially, the min-heap contains all seat numbers from 1 to n. The reserve() operation would simply extract the smallest element from the min-heap. The unreserve(int seatNumber) operation would add the seatNumber back into the min-heap.

Code (Python)

import heapq

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

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

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

Time and Space Complexity

  • Time Complexity:
    • SeatManager(int n): O(n) to initialize the list and O(n) to heapify, so O(n) in total.
    • reserve(): O(log n) to extract the smallest element from the min-heap.
    • unreserve(int seatNumber): O(log n) to insert the element into the min-heap.
  • Space Complexity: O(n) to store the min-heap.

Edge Cases

  • n = 1: The min-heap solution still works fine.
  • reserve() called many times: The min-heap will shrink as reserve() is called. The time complexity of reserve() will not be affected, but unreserve() calls can become more expensive if many elements have been reserved.
  • unreserve() called many times: The min-heap will grow as unreserve() is called. The time complexity of unreserve() will not be affected, but reserve() calls can become more expensive if many elements have been unreserved.

In summary, the optimal solution using a min-heap provides a significantly better time complexity for the reserve() and unreserve() operations compared to the naive boolean array approach, making it more suitable for a large number of seats and frequent reservation/unreservation requests.