Seat Reservation Manager

class SeatController {
    int current;
    
    set<int> freeSeats;
    
public:
    SeatController(int n) {
        current = 1;
    }
    
    int reserveSeat() {
        if (!freeSeats.empty()) {
            int lowestSeat = *freeSeats.begin();
            freeSeats.erase(freeSeats.begin());
            return lowestSeat;
        }
    
        int seat = current;
        current++;
        return seat;
    }
    
    void returnSeat(int seatNumber) {
        freeSeats.insert(seatNumber);
    }
};

The solution implements a class named SeatController to manage seat reservations efficiently, using C++ as the programming language. This class utilizes an integer current to track the next available seat and a set<int> to manage seats that become available when they are returned. Here’s a breakdown of how the SeatController operates:

• Initialization:

  • SeatController(int n): Initializes the current seat to 1, effectively setting the first available seat when an instance is created.

• Reserve a Seat:

  • int reserveSeat(): This method checks if there are any seats in the freeSeats set. If available, it reserves the lowest numbered seat, removes it from the set, and returns this seat number. If no seats are available in the set, it reserves the seat number held by current, increments current, and returns the seat number.

• Return a Seat:

  • void returnSeat(int seatNumber): When a seat is no longer needed, this method is used to return a seat by inserting the seatNumber back into the freeSeats set. This makes the seat available again for future reservations.

This approach ensures efficient management of seat reservations and returns, allowing for quick allocation of the lowest available seat numbers and handling of dynamically freed seats.

class SeatAllocation {
    int current;
    
    TreeSet<Integer> freeSeats;
    
    public SeatAllocation(int n) {
        current = 1;
        freeSeats = new TreeSet<>();
    }
    
    public int allocate() {
        if (!freeSeats.isEmpty()) {
            int seat = freeSeats.first();
            freeSeats.remove(seat);
            return seat;
        }
        int seat = current;
        current++;
        return seat;
    }
    
    public void release(int seatNumber) {
        freeSeats.add(seatNumber);
    }
}

This Java solution handles seat reservation management using an efficient approach. The SeatAllocation class utilizes a TreeSet to keep track of free seats which ensures that the seats are always sorted, allowing for quick allocations and releases.

• Initialize the SeatAllocation class with the total number of seats. This sets the current seat to 1 and prepares a new TreeSet, freeSeats, to store available seats that have been released.

• The allocate method checks if there are any seats in freeSeats. If available, it retrieves and removes the smallest seat number from freeSeats, which represents the lowest available seat number. If no seats are free, it assigns the seat number stored in current, then increments current for the next call.

• The release method is straightforward and simply adds the released seat number back to the freeSeats set, making it available for future allocations.

This setup ensures that the system efficiently manages seat allocations and keeps track of available seats, optimizing both operations based on the scenario.

from sortedcontainers import SortedSet
    
class ReservationManager:
    def __init__(self, size):
        # Initialize smallest unreserved seat index
        self.current_seat = 1
    
        # Store for all available seats
        self.unreserved_seats = SortedSet()
    
    def book_seat(self):
        # Check and remove the smallest available seat
        if self.unreserved_seats:
            smallest_seat = self.unreserved_seats.pop(0)
            return smallest_seat
    
        # Book by current index and update
        smallest_seat = self.current_seat
        self.current_seat += 1
        return smallest_seat
    
    def free_seat(self, seat_id):
        # Return seat to the unreserved set
        self.unreserved_seats.add(seat_id)

The solution implements a ReservationManager class to manage seat reservations. Here's an outline of how the defined class operates using Python and the SortedSet from the sortedcontainers module:

• Initialization of the Reservation Manager:

  • __init__: Initializes with a given size for the number of seats. It sets current_seat to 1, indicating the first seat to be reserved sequentially without previous reservations. It also initializes unreserved_seats as a SortedSet to keep track of seats that have been freed up and are available for reservation again.

• Booking a Seat:

  • book_seat: This method checks if there are any unreserved seats available in unreserved_seats. If available, it removes and returns the smallest number seat from the set, ensuring that the lowest numbered seat is always given out first. If no seats are unreserved, it books the current current_seat and then increments it to prepare for the next booking.

• Freeing a Seat:

  • free_seat: This method takes a seat_id as an argument and adds it back into the unreserved_seats set. This action makes the seat available again for future bookings.

The implementation guarantees that seating allocation is efficient, with minimal seat numbers allocated first, and seats that become available again are promptly reused. The use of SortedSet allows efficient insertion and removal of seats while maintaining order.