1845. Seat Reservation Manager

MediumDesignHeap (Priority Queue)
Leetcode Link

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:

  1. Initialization (SeatManager(int n)): The constructor of the system takes an integer n which represents the total number of seats. It should set up the initial state with all seats available for reservation.

  2. 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).

  3. Unreserve (void unreserve(int seatNumber)): This function takes an integer seatNumber 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 the heapq 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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

A heap is a ...?

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 our SeatManager with an array (list) containing all possible seat numbers. This array is denoted as self.q (representing a queue) and holds integers from 1 to n inclusive. The heapify function is then called on self.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 index 0.

    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 the heappop function on our heap self.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, the heappush function is used. It takes the seat number and adds it back to our heap self.q. The heappush 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What data structure does Breadth-first search typically uses to store intermediate states?

Example 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 with self.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 calls heappop(self.q), which removes the root of the heap, the smallest element: seat 1.
  • The reserve method then returns this value, so seat 1 is now reserved.
  • The self.q looks like [2, 3, 4, 5] now, with 2 being the next available seat as the root.

If we reserve again:

  • Calling reserve() pops the root, which is now seat 2.
  • The method returns 2, making that seat reserved.
  • The self.q is now [3, 4, 5] with 3 at the root.

Now, let's assume a client wants to unreserve seat 2. They call unreserve(2):

  • The unreserve method calls heappush(self.q, 2), which adds seat 2 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 pop 2 from the heap again (even though we put it back earlier).
  • The reserve method returns 2 once more, reserving it again.
  • The self.q state is [3, 4, 5] with seat 3 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
Not Sure What to Study? Take the 2-min Quiz：

How many ways can you arrange the three letters A, B and C?

Time and Space Complexity

Time Complexity

  • init method: O(n) - Constructing the heap of size n takes O(n) time.
  • reserve method: O(log n) - Popping the smallest element from the heap takes O(log n) time, where n 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) where n 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.

Fast Track Your Learning with Our Quick Skills Quiz:

A person thinks of a number between 1 and 1000. You may ask any number questions to them, provided that the question can be answered with either "yes" or "no".

What is the minimum number of questions you needed to ask so that you are guaranteed to know the number that the person is thinking?

Recommended Readings

Heap Fundamentals

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 - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

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 Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫