Seat Reservation Manager

XXX. Seat Manager

Heap

Greedy

Simulation

Problem Statement:

Design a system to manage the reservation and unreservation of seats in a theater.

Implement the following functions:

• reserve(): Reserves the lowest available seat number and returns it.
• unreserve(int seatNumber): Unreserves the seat with the given number, making it available for future reservations.

Algorithm:

1. Use a min-heap to keep track of unreserved seats in sorted order.
2. Maintain a marker to point to the smallest-numbered seat that has not yet been reserved or added to the heap.
3. reserve():
   • If the heap is not empty, pop the smallest seat from the heap.
   • Otherwise, use the current marker value as the seat number and increment the marker.
4. unreserve(seatNumber):
   • Add the seat number back to the heap, maintaining sorted order.

Complexity:

Time Complexity:

• reserve(): O(log k), where k is the size of the heap.
• unreserve(): O(log k), where k is the size of the heap.

Space Complexity: O(k), where k is the number of seats that have been unreserved.

Java Implementation:

import java.util.PriorityQueue;

class SeatManager {
    int marker; // Points to the smallest unreserved seat.
    PriorityQueue availableSeats; // Min-heap to store unreserved seats.

    public SeatManager(int n) {
        marker = 1; // Start with the smallest seat number.
        availableSeats = new PriorityQueue<>();
    }

    public int reserve() {
        if (!availableSeats.isEmpty()) {
            // Get the smallest-numbered seat from the heap.
            return availableSeats.poll();
        }
        // Otherwise, use the marker value.
        return marker++;
    }

    public void unreserve(int seatNumber) {
        // Add the seat back to the heap.
        availableSeats.offer(seatNumber);
    }
}
                

Python Implementation:

import heapq

class SeatManager:
    def __init__(self, n: int):
        self.marker = 1  # Points to the smallest unreserved seat.
        self.available_seats = []  # Min-heap to store unreserved seats.

    def reserve(self) -> int:
        if self.available_seats:
            # Get the smallest-numbered seat from the heap.
            return heapq.heappop(self.available_seats)
        # Otherwise, use the marker value.
        self.marker += 1
        return self.marker - 1

    def unreserve(self, seatNumber: int) -> None:
        # Add the seat back to the heap.
        heapq.heappush(self.available_seats, seatNumber)
                

C++ Implementation:

#include 
#include 

class SeatManager {
    int marker; // Points to the smallest unreserved seat.
    std::priority_queue, std::greater> availableSeats; // Min-heap to store unreserved seats.

public:
    SeatManager(int n) {
        marker = 1; // Start with the smallest seat number.
    }

    int reserve() {
        if (!availableSeats.empty()) {
            // Get the smallest-numbered seat from the heap.
            int seatNumber = availableSeats.top();
            availableSeats.pop();
            return seatNumber;
        }
        // Otherwise, use the marker value.
        return marker++;
    }

    void unreserve(int seatNumber) {
        // Add the seat back to the heap.
        availableSeats.push(seatNumber);
    }
};