1845.seat-reservation-manager.md

1845. Seat Reservation Manager

Heap (Naive)

We initailze a priority queue with all the seats. When we reserve a seat, we poll the top element from the queue. When we unreserve a seat, we add the seat number back to the queue.

class SeatManager(private val n: Int) {

    private val seats = PriorityQueue<Int>()

    init {
        (1..n).forEach {
            seats.add(it)
        }
    }

    fun reserve(): Int {
        return seats.poll()
    }

    fun unreserve(seatNumber: Int) {
        seats.add(seatNumber)
    }
}

• Time Complexity: O(log n) for reserve and unreserve operations, and O(n) for initialization, total is O(n log n).
• Space Complexity: O(n) for priority queue.

Heap (Optimal)

Another solution is to use a variable currentSeat to represent the smallest unreserved seat number, if we don't unreverse the seat, then the smallest-numbered unreserved seat is always monotonic increasing. We can just use it and increase it by 1 when we reserve a seat.

It guarantees that we invoke unreserve(x) after reserve(), so x < currentSeat. We use a min heap to maintain the unreserved seats, similar idea as 2336. Smallest Number in Infinite Set.

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...
            |---> curSeat
|--heap--|

class SeatManager(private val n: Int) {

    private var currentSeat = 1
    private val unreservedSeats = PriorityQueue<Int>()
    
    fun reserve(): Int {
        if (unreservedSeats.isEmpty()) {
            return currentSeat++
        }
        return unreservedSeats.poll()
    }

    fun unreserve(seatNumber: Int) {
        unreservedSeats.add(seatNumber)
    }
}

• Time Complexity: O(log n) for reserve and unreserve operations.
• Space Complexity: O(q) for priority queue.