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
reserve
, it is guaranteed that there will be at least one unreserved seat.unreserve
, it is guaranteed that seatNumber
will be reserved.10^5
calls in total will be made to reserve
and unreserve
.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
.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
.
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
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).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.
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)
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.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.