Leetcode 1845: Seat Reservation Manager
Design a system to manage the reservation state of n seats numbered from 1 to n. Implement the SeatManager class to handle reserving and unreserving seats. The class should be able to return the smallest available seat when reserved, and make seats available again when unreserved.
Problem
Approach
Steps
Complexity
Input: You are given an integer n, which represents the number of seats. The operations are called as a sequence of commands where reserve() reserves the smallest available seat and unreserve(seatNumber) unreserves a seat.
Example: [5], [], [], [2], [], [], [], [], [5]
Constraints:
• 1 <= n <= 10^5
• 1 <= seatNumber <= n
• At least one unreserved seat will be available for each reserve call.
• seatNumber will always refer to a reserved seat for each unreserve call.
Output: For each call to reserve, return the smallest available seat number. For each call to unreserve, no return value is expected, but the seat is made available again.
Example: [null, 1, 2, null, 2, 3, 4, 5, null]
Constraints:
Goal: The system should efficiently handle reserving and unreserving seats while keeping track of the smallest available seat number.
Steps:
• Use a priority queue to keep track of available seats.
• Initialize the seats from 1 to n, making them all available initially.
• On calling reserve(), pop the smallest seat from the queue.
• On calling unreserve(), push the seat back into the priority queue.
Goal: The input will always guarantee that there is at least one available seat for reserve calls, and the seatNumber for unreserve will always refer to a seat that has been reserved.
Steps:
• 1 <= n <= 10^5
• 1 <= seatNumber <= n
Assumptions:
• The SeatManager class is initialized correctly with n seats.
• The input operations are valid according to the problem constraints.
• Input: [5], [], [], [2], [], [], [], [], [5]
• Explanation: The SeatManager starts with 5 seats. After reserving and unreserving as per the sequence, the smallest available seats are allocated, and seats are made available again after unreserving.
Approach: We can use a priority queue to efficiently manage seat reservations. The smallest seat number can be retrieved in O(log n) time, and unreserving a seat also takes O(log n) time.
Observations:
• A priority queue (min-heap) is a suitable data structure to manage the smallest available seat.
• We will maintain a priority queue for unreserved seats and use a simple counter to track the next available seat.
Steps:
• Initialize a priority queue and a counter for the next seat.
• For each reserve operation, check the priority queue for the smallest available seat and return it.
• For each unreserve operation, return the seat to the priority queue.
Empty Inputs:
• The input will always contain a valid n and a valid sequence of operations.
Large Inputs:
• The solution must handle the largest value of n (100,000) efficiently.
Special Values:
• Consider cases where unreserving a seat happens immediately after reserving the last available one.
Constraints:
• The operations are guaranteed to follow valid rules, with no unreserve called on an unreserved seat.
int i, n;
priority_queue<int, vector<int>, greater<int>> pq;
SeatManager(int n) {
i = 1;
this->n = n;
}
int reserve() {
if(pq.empty() && i > n) {
return -1;
}
if(pq.empty()) {
i++;
return i - 1;
}
int tmp = pq.top();
pq.pop();
return tmp;
}
void unreserve(int no) {
if(no == i - 1) {
i--;
return;
}
pq.push(no);
}
};
/**
* Your SeatManager object will be instantiated and called as such:
* SeatManager* obj = new SeatManager(n);
* int param_1 = obj->reserve();
* obj->unreserve(seatNumber);
1 : Variable Initialization
int i, n;
Defines two variables: `i` (current seat index) and `n` (total number of seats).
2 : Priority Queue Declaration
priority_queue<int, vector<int>, greater<int>> pq;
Declares a priority queue `pq` to manage available seat numbers in increasing order.
3 : Constructor
SeatManager(int n) {
Constructor that initializes the `SeatManager` object with a total of `n` seats.
4 : Constructor Logic
i = 1;
Sets the starting seat index `i` to 1.
5 : Constructor Logic
this->n = n;
Sets the total number of seats `n` based on the input argument.
6 : Reserve Function Start
int reserve() {
Defines the `reserve` function that reserves a seat and returns its seat number.
7 : Condition Check for Empty Queue and Full Seats
if(pq.empty() && i > n) {
Checks if the priority queue is empty and all seats have been reserved.
8 : Return Statement
return -1;
Returns -1 if no seats are available.
9 : Condition Check for Empty Queue
}
End of the first if-condition.
10 : Reserve Logic
if(pq.empty()) {
Checks if the priority queue is empty and there are still unreserved seats.
11 : Seat Allocation
i++;
Increments the seat index `i` to allocate the next available seat.
12 : Seat Return
return i - 1;
Returns the seat number `i - 1` after allocating it.
13 : Priority Queue Logic
int tmp = pq.top();
Gets the seat number at the top of the priority queue (the smallest available seat).
14 : Priority Queue Update
pq.pop();
Removes the seat number from the priority queue after it has been reserved.
15 : Seat Return
return tmp;
Returns the reserved seat number from the priority queue.
16 : Unreserve Function Start
void unreserve(int no) {
Defines the `unreserve` function that releases a reserved seat.
17 : Condition Check for Last Reserved Seat
if(no == i - 1) {
Checks if the seat to be unreserved is the last reserved seat.
18 : Seat Release
i--;
Decrements the seat index `i` to reflect that the last reserved seat is now available.
19 : Unreserve Completion
return;
Exits the function since the seat has been unreserved.
20 : Priority Queue Insertion
pq.push(no);
Adds the unreserved seat number back to the priority queue.
Best Case: O(log n)
Average Case: O(log n)
Worst Case: O(log n)
Description: Both reserve and unreserve operations take O(log n) time due to the priority queue operations.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n) as we store up to n seats in the priority queue.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus