Seat Reservation Manager - Leetcode Solution

Problem Description:

The problem is to design a seat reservation manager for a movie theater. The theater has a total of n rows of seats, each row consisting of m seats labeled from 1 to m. Some seats are already reserved, and some are available.

You need to implement the SeatManager class:

SeatManager(int n, int m) Initializes a SeatManager object that will manage n rows of m seats each, labeled from 1 to m. int reserve() - Returns the label of the seat that is reserved for the next person who comes in. The seats are allocated according to the following rules:

The seat closest to the front is assigned, followed by the seat closest to the front in the next row, and so on until all seats are taken. If there are multiple available seats, the one with the smallest label is assigned. None of the reserved seats is assigned again. void unreserve(int seatNumber) - Unreserves the seat with the given seatNumber.

Solution:

We need to create a seat manager class which will manage the seat reservation of a movie theatre. We can implement the SeatManager class using a priority queue and HashSet data structures.

First, we will create a priority queue of all seat numbers that are available. We can prioritize the seats based on their row and seat numbers. Seat numbers in the front rows should be prioritized over seats in back rows. Within the same row, we should prioritize the seats with the smallest seat number.

We can use a HashSet to keep track of the reserved seats so that we do not accidentally reserve a seat that is already reserved.

The constructor of the class will initialize the priority queue with all the seat numbers, and the HashSet will be empty since no seats are reserved initially.

The reserve() method will pop the smallest seat number from the priority queue and add it to the HashSet to mark it as reserved. The seat number is then returned.

The unreserve(seatNumber) method will remove the seat number from the HashSet and add it back to the priority queue to make it available again.

Here’s the implementation:

class SeatManager { PriorityQueue<Integer> pq; Set<Integer> set; public SeatManager(int n, int m) { pq = new PriorityQueue<>(); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { pq.offer((i - 1) * m + j); } } set = new HashSet<>(); }

public int reserve() {
    int nextSeat = pq.poll();
    set.add(nextSeat);
    return nextSeat;
}

public void unreserve(int seatNumber) {
    set.remove(seatNumber);
    pq.offer(seatNumber);
}

}

Time complexity:

The time complexity of reserve() method is O(log(n*m)) as it involves removing the smallest seat number from the priority queue.

The time complexity of unreserve() method is O(1) as it only involves removing the seat number from the HashSet and adding it back to the priority queue.

Space complexity:

The space complexity of the SeatManager class is O(nm) since we store all seat numbers in the priority queue. The HashSet can also have up to nm elements in the worst case.

1