Seat Reservation Manager
MedPrompt
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 aSeatManagerobject that will managenseats numbered from1ton. 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 givenseatNumber.
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 <= 1051 <= 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 thatseatNumberwill be reserved. - At most
105calls in total will be made toreserveandunreserve.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach uses a boolean array to keep track of the status of each seat. A true value at an index indicates the seat is reserved, while false indicates it's available.
Algorithm
SeatManager(n):- Create a boolean array
reservedof sizen+1.
- Create a boolean array
reserve():- Iterate
ifrom 1 ton. - If
reserved[i]isfalse:- Set
reserved[i]totrue. - Return
i.
- Set
- Iterate
unreserve(seatNumber):- Set
reserved[seatNumber]tofalse.
- Set
Walkthrough
Initialization
In the SeatManager(n) constructor, we create a boolean array seats of size n + 1 (to accommodate 1-based indexing). We initialize all entries to false, signifying that all seats from 1 to n are initially available.
reserve()
To reserve the smallest-numbered seat, we perform a linear scan through the seats array, starting from index 1. The first index i we find where seats[i] is false corresponds to the smallest available seat. We then mark this seat as reserved by setting seats[i] = true and return the seat number i.
unreserve(seatNumber)
To unreserve a seat, we simply access the corresponding index in the array and set its value back to false. This is a constant-time operation.
class SeatManager { private boolean[] reserved; private int n; public SeatManager(int n) { this.n = n; this.reserved = new boolean[n + 1]; // Using 1-based indexing } public int reserve() { for (int i = 1; i <= n; i++) { if (!reserved[i]) { reserved[i] = true; return i; } } return -1; // Should not happen based on problem constraints } public void unreserve(int seatNumber) { if (seatNumber >= 1 && seatNumber <= n) { reserved[seatNumber] = false; } }}Complexity
Time
- **Constructor**: O(n) to initialize the boolean array. - **`reserve()`**: O(n) because in the worst case, we might have to scan the entire array to find an available seat. - **`unreserve()`**: O(1) for direct array access.
Space
O(n) to store the state of `n` seats in the boolean array.
Trade-offs
Pros
Simple to understand and implement.
unreserveis very fast, taking O(1) time.
Cons
The
reserveoperation is slow, with a time complexity of O(n). This can lead to a 'Time Limit Exceeded' error on platforms with strict time limits, especially given that n can be up to 10^5.
This approach maintains all available seats in a min-heap data structure. A min-heap is ideal because it always provides the smallest element (the smallest-numbered available seat) in logarithmic time.
Algorithm
SeatManager(n):- Create a
PriorityQueue<Integer>namedavailableSeats. - For
ifrom 1 ton, additoavailableSeats.
- Create a
reserve():- Call
availableSeats.poll()and return the result.
- Call
unreserve(seatNumber):- Call
availableSeats.add(seatNumber).
- Call
Walkthrough
Initialization
In the SeatManager(n) constructor, we create a PriorityQueue (which acts as a min-heap in Java). We then populate it with all seat numbers from 1 to n. This ensures all seats are initially marked as available and are ordered by their number.
reserve()
The reserve operation becomes very simple. The smallest-numbered available seat is always at the root of the min-heap. We can retrieve and remove it using the poll() method, which has a logarithmic time complexity.
unreserve(seatNumber)
To unreserve a seat, we add its number back into the min-heap using the add() or offer() method. This operation also takes logarithmic time as the heap needs to maintain its property.
import java.util.PriorityQueue; class SeatManager { private PriorityQueue<Integer> availableSeats; public SeatManager(int n) { availableSeats = new PriorityQueue<>(); for (int i = 1; i <= n; i++) { availableSeats.add(i); } } public int reserve() { return availableSeats.poll(); } public void unreserve(int seatNumber) { availableSeats.add(seatNumber); }}Complexity
Time
- **Constructor**: O(n log n) to add `n` elements to the priority queue. It can be optimized to O(n) by creating a list first and then initializing the priority queue from it. - **`reserve()`**: O(log k), where `k` is the number of available seats. In the worst case, `k` can be `n`. - **`unreserve()`**: O(log k).
Space
O(n) to store all `n` seat numbers in the priority queue at the beginning.
Trade-offs
Pros
Significantly faster
reserveoperation compared to the linear scan approach.Well-suited for the problem constraints.
Cons
Requires O(n) space from the start, which might be suboptimal if
nis very large and the number of operations is small.The constructor takes O(n log n) or O(n) time, which could be a factor in some scenarios.
This is the most efficient approach. It leverages the fact that seats are initially reserved in increasing order (1, 2, 3, ...). We only need to use a data structure to manage the "gaps" created by unreserve operations.
Algorithm
SeatManager(n):- Initialize an integer
nextAvailableSeat = 1. - Initialize an empty
PriorityQueue<Integer>unreservedSeats.
- Initialize an integer
reserve():- If
unreservedSeatsis not empty:- Return
unreservedSeats.poll().
- Return
- Else:
- Return
nextAvailableSeat++.
- Return
- If
unreserve(seatNumber):- Add
seatNumbertounreservedSeats.
- Add
Walkthrough
Data Structures
We use two main components:
- An integer counter,
nextAvailableSeat, initialized to 1. This tracks the next seat to be given out from the contiguous block of unreserved seats. - A min-heap (
PriorityQueue),unreservedSeats, which is initially empty. This heap will store any seat numbers that are unreserved and are smaller thannextAvailableSeat.
Initialization
The constructor is very lightweight. It just initializes nextAvailableSeat to 1 and creates an empty PriorityQueue.
reserve()
When a reservation is requested, we first check if our unreservedSeats heap is empty.
- If it's not empty, it means there's a previously unreserved seat available that has a smaller number than our
nextAvailableSeatcounter. Wepoll()from the heap and return this seat number. - If the heap is empty, it means there are no "gaps" to fill. The smallest available seat is the one pointed to by our counter. We return
nextAvailableSeatand then increment it for the next call.
unreserve(seatNumber)
When a seat is unreserved, we simply add its number to the unreservedSeats min-heap. This seat will then be available for a future reserve() call and will be prioritized by the heap if it's the smallest available.
import java.util.PriorityQueue; class SeatManager { private PriorityQueue<Integer> unreservedSeats; private int nextAvailableSeat; public SeatManager(int n) { // n is not strictly needed for this implementation but is part of the signature this.unreservedSeats = new PriorityQueue<>(); this.nextAvailableSeat = 1; } public int reserve() { if (!unreservedSeats.isEmpty()) { return unreservedSeats.poll(); } return nextAvailableSeat++; } public void unreserve(int seatNumber) { unreservedSeats.add(seatNumber); }}Complexity
Time
- **Constructor**: O(1). - **`reserve()`**: O(log k), where `k` is the number of elements in the priority queue (i.e., the number of seats that have been unreserved). - **`unreserve()`**: O(log k).
Space
O(k), where `k` is the maximum number of seats that are in the unreserved state at any given time. In the worst case, this is the total number of `unreserve` calls, which is bounded by 10^5. This is more space-efficient than the previous approaches if `n` is much larger than the number of calls.
Trade-offs
Pros
Extremely fast O(1) constructor.
Optimal time complexity for
reserveandunreserveoperations.Optimal space complexity, as it only stores what's necessary. The space used is proportional to the number of unreserved seats, not the total number of seats
n.
Cons
Slightly more complex logic than the other approaches, but the benefits in performance are substantial.
Solutions
Solution
public class SeatManager { private SortedSet < int > availableSeats ; public SeatManager ( int n ) { availableSeats = new SortedSet < int >(); for ( int i = 1 ; i <= n ; i ++) { availableSeats . Add ( i ); } } public int Reserve () { int reservedSeat = availableSeats . Min ; availableSeats . Remove ( reservedSeat ); return reservedSeat ; } public void Unreserve ( int seatNumber ) { availableSeats . Add ( seatNumber ); } } /** * Your SeatManager object will be instantiated and called as such: * SeatManager obj = new SeatManager(n); * int param_1 = obj.Reserve(); * obj.Unreserve(seatNumber); */class SeatManager { private PriorityQueue < Integer > q = new PriorityQueue <>(); public SeatManager ( int n ) { for ( int i = 1 ; i <= n ; ++ i ) { q . offer ( i ); } } public int reserve () { return q . poll (); } public void unreserve ( int seatNumber ) { q . offer ( seatNumber ); } } /** * Your SeatManager object will be instantiated and called as such: * SeatManager obj = new SeatManager(n); * int param_1 = obj.reserve(); * obj.unreserve(seatNumber); */class SeatManager : def __init__ ( self , n : int ): self . q = list ( range ( 1 , n + 1 )) heapify ( self . q ) 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)class SeatManager { public: SeatManager ( int n ) { for ( int i = 1 ; i <= n ; ++ i ) { q . push ( i ); } } int reserve () { int seat = q . top (); q . pop (); return seat ; } void unreserve ( int seatNumber ) { q . push ( seatNumber ); } private: priority_queue < int , vector < int > , greater < int >> q ; }; /** * Your SeatManager object will be instantiated and called as such: * SeatManager* obj = new SeatManager(n); * int param_1 = obj->reserve(); * obj->unreserve(seatNumber); */Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.