1845. Seat Reservation Manager
Problem Description
The problem involves designing a system to manage seat reservations for a series of seats that are sequentially numbered from 1 through n, where n is the total number of seats available. The system should support two key operations: reserving a seat and unreserving a seat. When a seat is reserved, it should be the seat with the smallest number currently available. Unreserving will return a previously reserved seat back into the pool of available seats.
The operations that the system needs to support are as follows:
-
Initialization (
SeatManager(int n)
): The constructor of the system takes an integern
which represents the total number of seats. It should set up the initial state with all seats available for reservation. -
Reserve (
int reserve()
): This operation should return the smallest-numbered seat that is currently unreserved, and then reserve it (making it no longer available for reservation). -
Unreserve (
void unreserve(int seatNumber)
): This function takes an integerseatNumber
and unreserves that specific seat, making it available again for future reservations.
Intuition
The solution to this problem requires an efficient data structure that can constantly provide the smallest-numbered available seat and also allow reserving and unreserving seats in a relatively fast manner. A min-heap is a suitable data structure for this problem as it can always provide the minimum element in constant time and supports insertion and deletion operations in logarithmic time. In Python, we have access to a min-heap implementation through the heapq
module.
Here's the intuition behind each part of the solution:
-
Initialization: We initialize the state by creating a list of all available seats. We then transform this list into a heap using the
heapify
function from theheapq
module. This sets up our min-heap, ensuring that we always have quick access to the smallest available seat number. -
Reserve: When reserving a seat, we pop the smallest element from the heap using the
heappop
function, which gets us the smallest-numbered seat available. This operation also removes this seat from the pool of available seats. -
Unreserve: To unreserve a seat, we push the seat number back into the min-heap using the
heappush
function. This means the seat is again counted among the available seats and can be reserved in a future operation.
Overall, the min-heap maintains the state of available seats, ensuring the system can efficiently handle the reservation state and seat allocations.
Learn more about Heap (Priority Queue) patterns.
Solution Approach
The solution to the problem uses a priority queue data structure, which is implemented using a heap in Python with the heapq
module. The heap is a specialized tree-based data structure that satisfies the heap property — in the case of a min-heap, the smallest element is at the root, making it easy to access it quickly.
Here's a walkthrough of the algorithm and data structures used in each method of the SeatManager
class:
-
Initialization (
__init__
method): We initialize ourSeatManager
with an array (list) containing all possible seat numbers. This array is denoted asself.q
(representing a queue) and holds integers from1
ton
inclusive. Theheapify
function is then called onself.q
to transform it into a heap. This operation rearranges the array into a heap structure, so it's ready to serve the smallest element, which will be at index0
.1def __init__(self, n: int): 2 self.q = list(range(1, n + 1)) 3 heapify(self.q)
-
Reserve (
reserve
method): To reserve a seat, we use theheappop
function on our heapself.q
. This function removes and returns the smallest element from the heap, which corresponds to the smallest-numbered available seat as per our problem statement. Since the heap property is maintained after the pop operation, the next smallest element will come to the front.1def reserve(self) -> int: 2 return heappop(self.q)
-
Unreserve (
unreserve
method): When a seat needs to be unreserved, theheappush
function is used. It takes the seat number and adds it back to our heapself.q
. Theheappush
function automatically rearranges elements in the heap to ensure the heap property is maintained after adding a new element.1def unreserve(self, seatNumber: int) -> None: 2 heappush(self.q, seatNumber)
The key insights in applying a min-heap for this solution are the constant time access to the minimum element and the logarithmic time complexity for insertion and deletion operations. The way the min-heap self-adjusts after a pop or push operation ensures that the sequence of available seats is always well-organized for the needs of the reserve
and unreserve
methods.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let us consider an example where n = 5
, which means that the SeatManager
is initialized with 5 seats available.
The SeatManager
is set up by calling SeatManager(5)
.
- When initialized (
__init__
), we start withself.q
listing seat numbers[1, 2, 3, 4, 5]
. - After applying
heapify(self.q)
,self.q
becomes a min-heap but remains[1, 2, 3, 4, 5]
since it is already in ascending order and satisfies the heap property (the smallest element is at the root).
When a client calls reserve()
for the first time:
- The
reserve
method callsheappop(self.q)
, which removes the root of the heap, the smallest element: seat1
. - The
reserve
method then returns this value, so seat1
is now reserved. - The
self.q
looks like[2, 3, 4, 5]
now, with2
being the next available seat as the root.
If we reserve again:
- Calling
reserve()
pops the root, which is now seat2
. - The method returns
2
, making that seat reserved. - The
self.q
is now[3, 4, 5]
with3
at the root.
Now, let's assume a client wants to unreserve seat 2
. They call unreserve(2)
:
- The
unreserve
method callsheappush(self.q, 2)
, which adds seat2
back to the heap. - The heap structure is maintained, and
self.q
automatically readjusts to[2, 3, 4, 5]
as it becomes the root again.
Next, if another reserve request comes:
- Calling
reserve()
now would pop2
from the heap again (even though we put it back earlier). - The
reserve
method returns2
once more, reserving it again. - The
self.q
state is[3, 4, 5]
with seat3
ready to be the next one reserved.
This example demonstrates how a min-heap structure is essential for efficiently managing the smallest seat number reservation and is perfectly suited to the requirements of the problem described. The ordering of the heap ensures that the smallest number is always at the root and can be reserved or unreserved in a consistent and predictable manner.
Solution Implementation
1import heapq # Importing heapq for heap operations
2
3class SeatManager:
4 def __init__(self, n: int):
5 # Initializing a list of seat numbers starting from 1 to n
6 self.available_seats = list(range(1, n + 1))
7 # Heapifying the list to create a min-heap
8 # In a min-heap, the smallest element is always at the root
9 heapq.heapify(self.available_seats)
10
11 def reserve(self) -> int:
12 # Reserving the smallest available seat number
13 # (i.e., popping the root element from the min-heap)
14 return heapq.heappop(self.available_seats)
15
16 def unreserve(self, seat_number: int) -> None:
17 # Releasing a previously reserved seat by adding it back into the heap
18 # and then rearranging the heap
19 heapq.heappush(self.available_seats, seat_number)
20 # The heappush function automatically maintains the heap property
21
22# An example on how to use the SeatManager class
23# obj = SeatManager(n)
24# seat_number = obj.reserve()
25# obj.unreserve(seat_number)
26
1import java.util.PriorityQueue;
2
3// SeatManager manages the reservation and releasing of seats
4public class SeatManager {
5
6 // PriorityQueue to store available seat numbers in ascending order
7 private PriorityQueue<Integer> availableSeats;
8
9 // Constructor initializes the PriorityQueue with all seat numbers
10 public SeatManager(int n) {
11 availableSeats = new PriorityQueue<>();
12 // Add all seats to the queue, seat numbers start from 1 to n
13 for (int seatNumber = 1; seatNumber <= n; seatNumber++) {
14 availableSeats.offer(seatNumber);
15 }
16 }
17
18 // reserve() method to reserve the seat with the lowest number
19 public int reserve() {
20 // Polling gets and removes the smallest available seat number
21 return availableSeats.poll();
22 }
23
24 // unreserve() method to put a seat number back into the queue
25 public void unreserve(int seatNumber) {
26 // Offering adds the seat number back to the available seats
27 availableSeats.offer(seatNumber);
28 }
29}
30
31// Example of how the SeatManager might be used:
32// SeatManager manager = new SeatManager(n);
33// int seatNumber = manager.reserve(); // Reserves the lowest available seat number
34// manager.unreserve(seatNumber); // Unreserves a seat, making it available again
35
1#include <queue>
2#include <vector>
3
4class SeatManager {
5public:
6 // Constructor that initializes the seat manager with a given number of seats.
7 SeatManager(int n) {
8 // Add all seats to the priority queue in ascending order.
9 for (int i = 1; i <= n; ++i) {
10 seats.push(i);
11 }
12 }
13
14 // Reserves the lowest-numbered seat that is available and returns the seat number.
15 int reserve() {
16 // Get the smallest available seat number from the priority queue.
17 int allocatedSeat = seats.top();
18 // Remove the seat from the priority queue as it is now reserved.
19 seats.pop();
20 // Return the reserved seat number.
21 return allocatedSeat;
22 }
23
24 // Unreserves a previously reserved seat so it can be used again in the future.
25 void unreserve(int seatNumber) {
26 // Add the seat back to the priority queue as it is now available.
27 seats.push(seatNumber);
28 }
29
30private:
31 // Priority queue to manage the available seats. Seats are sorted in ascending order.
32 std::priority_queue<int, std::vector<int>, std::greater<int>> seats;
33};
34
35/**
36 * This code snippet shows how to create an instance of the SeatManager and
37 * use its reserve and unreserve methods.
38 *
39 * // Initialization
40 * SeatManager* seatManager = new SeatManager(n);
41 *
42 * // Reserve a seat
43 * int reservedSeatNumber = seatManager->reserve();
44 *
45 * // Unreserve a specific seat
46 * seatManager->unreserve(seatNumber);
47 *
48 * // Remember to free allocated memory if it's no longer needed, to avoid memory leaks
49 * delete seatManager;
50 */
51
1// Initialize variables for seat management.
2let seatsArray: number[] = [];
3
4// Function that initializes the seat manager with a given number of seats.
5function initializeSeatManager(n: number): void {
6 // Ensure the seats array is empty before initialisation.
7 seatsArray = [];
8 // Add all seats to the array in ascending order.
9 for (let i = 1; i <= n; ++i) {
10 seatsArray.push(i);
11 }
12 // Sort the array to maintain the priority queue behavior.
13 // This is to ensure the smallest number is always at the start of the array.
14 seatsArray.sort((a, b) => a - b);
15}
16
17// Function that reserves the lowest-numbered seat that is available and returns the seat number.
18function reserve(): number {
19 // Shift the first element from the array and return it,
20 // representing the reservation of the lowest available seat.
21 let allocatedSeat = seatsArray.shift();
22 // Return the reserved seat number.
23 return allocatedSeat ?? -1; // Returns -1 if no seat is available (in a case where the array is empty).
24}
25
26// Function to unreserve a previously reserved seat so it can be used again in the future.
27function unreserve(seatNumber: number): void {
28 // Add the seat number back to the array.
29 seatsArray.push(seatNumber);
30 // Sort the array to re-establish priority queue order.
31 seatsArray.sort((a, b) => a - b);
32}
33
34// Usage example:
35// Initialize the seat manager with a number of seats.
36initializeSeatManager(10);
37
38// Reserve a seat.
39let reservedSeatNumber = reserve();
40
41// Unreserve a specific seat.
42unreserve(reservedSeatNumber);
43
44// Note: In a real implementation, care should be taken to handle errors
45// or exceptional conditions, such as trying to unreserve a seat that has not been reserved.
46
Time and Space Complexity
Time Complexity
- init method: O(n) - Constructing the heap of size
n
takesO(n)
time. - reserve method: O(log n) - Popping the smallest element from the heap takes
O(log n)
time, wheren
is the number of unreserved seats. - unreserve method: O(log n) - Pushing an element into the heap takes
O(log n)
time.
Space Complexity
- The space complexity for the entire
SeatManager
is O(n) wheren
is the number of seats. This accounts for the heap that stores the seat numbers.
Learn more about how to find time and space complexity quickly using problem constraints.
How many times is a tree node visited in a depth first search?
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos heap svg Priority Queue and Heap What is the relationship between priority queue and heap Priority Queue is an Abstract Data Type and Heap is the concrete data structure we use to implement a priority queue Priority Queue A priority queue
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.