Problem Description

The Seat Reservation Manager problem asks you to design a system to efficiently manage seat reservations in a theater with n seats, numbered from 1 to n. The system must support two operations:

• reserve(): Reserves the smallest-numbered unreserved seat and returns its number.
• unreserve(seatNumber): Unreserves the given seat, making it available for future reservations.

The key constraints are:

• There are always enough seats to perform a reserve() operation.
• All seat numbers are unique and in the range [1, n].
• Unreserving a seat makes it available again, and reserve() must always return the lowest available seat number.

The challenge is to implement these operations efficiently, especially as the number of seats and operations grows large.

Thought Process

At first glance, we might think to use a simple list or array to track which seats are reserved or unreserved. For example, we could use a boolean array where True means reserved and False means available.

However, if we use this approach, every time we call reserve(), we would have to scan the entire array from the beginning to find the smallest unreserved seat. This is inefficient (O(n) per operation), especially if n is large.

To optimize, we need a data structure that allows us to:

• Quickly find and remove the smallest available seat number (reserve()).
• Quickly add a seat number back into the pool of available seats (unreserve(seatNumber)).

The min-heap (priority queue) data structure is ideal for this, as it always gives us the smallest element in O(log n) time and allows for efficient insertions.

Solution Approach

We design our seat manager with the following steps:

1. Initialize a min-heap:
   • We use a min-heap to store all seat numbers that have been unreserved (made available again).
   • We also keep a pointer, nextAvailable, initialized to 1, indicating the next seat number that has not been reserved yet.
2. reserve():
   • If the min-heap is not empty, pop and return the smallest seat number from the heap.
   • If the heap is empty, return nextAvailable and increment it by 1.
3. unreserve(seatNumber):
   • Push the seat number back into the min-heap so it becomes available for future reservations.

This structure ensures both operations are efficient:

• reserve() is O(log n) if using the heap, or O(1) if just incrementing nextAvailable.
• unreserve() is always O(log n) because of the heap insertion.

This approach is both simple and highly efficient.

Example Walkthrough

Let's walk through an example with n = 5:

1. reserve() returns 1 (nextAvailable becomes 2)
2. reserve() returns 2 (nextAvailable becomes 3)
3. unreserve(1): 1 is pushed into the heap.
4. reserve(): heap is not empty, so pop 1 from heap and return it.
5. reserve(): heap is empty, so return 3 (nextAvailable becomes 4)
6. reserve(): return 4 (nextAvailable becomes 5)
7. reserve(): return 5 (nextAvailable becomes 6)

The sequence of returned seat numbers will be: 1, 2, 1, 3, 4, 5.

Notice how unreserving seat 1 made it the next to be reserved, as it's the smallest available.

Time and Space Complexity

Brute-force approach:

• Time: O(n) per reserve() (scanning for the first unreserved seat)
• Space: O(n) (for the array tracking status)

• Time: O(log n) per reserve() if using the heap, O(1) if just incrementing nextAvailable; O(log n) for unreserve()
• Space: O(n) (for the heap and the nextAvailable pointer)

The min-heap ensures that both operations are fast, even for large n and many operations.

Summary

The Seat Reservation Manager problem is efficiently solved by combining a min-heap to track unreserved seats and a pointer for the next available seat. This approach guarantees that reserve() always returns the smallest available seat in O(log n) time or better, and unreserve() is also efficient. The solution is elegant because it leverages standard data structures for optimal performance and simplicity.

Code Implementation

import heapq

class SeatManager:
    def __init__(self, n: int):
        self.available = []
        self.nextAvailable = 1
        self.n = n

    def reserve(self) -> int:
        if self.available:
            return heapq.heappop(self.available)
        seat = self.nextAvailable
        self.nextAvailable += 1
        return seat

    def unreserve(self, seatNumber: int) -> None:
        heapq.heappush(self.available, seatNumber)
      

#include <queue>
#include <vector>

class SeatManager {
    priority_queue<int, vector<int>, greater<int>> available;
    int nextAvailable;
    int n;
public:
    SeatManager(int n) {
        this->n = n;
        nextAvailable = 1;
    }
    
    int reserve() {
        if (!available.empty()) {
            int seat = available.top();
            available.pop();
            return seat;
        }
        return nextAvailable++;
    }
    
    void unreserve(int seatNumber) {
        available.push(seatNumber);
    }
};
      

import java.util.PriorityQueue;

class SeatManager {
    private PriorityQueue<Integer> available;
    private int nextAvailable;
    private int n;

    public SeatManager(int n) {
        this.n = n;
        this.nextAvailable = 1;
        this.available = new PriorityQueue<>();
    }
    
    public int reserve() {
        if (!available.isEmpty()) {
            return available.poll();
        }
        return nextAvailable++;
    }
    
    public void unreserve(int seatNumber) {
        available.offer(seatNumber);
    }
}
      

class MinHeap {
    constructor() {
        this.heap = [];
    }
    push(val) {
        this.heap.push(val);
        this._bubbleUp();
    }
    pop() {
        if (this.heap.length === 0) return null;
        const min = this.heap[0];
        const last = this.heap.pop();
        if (this.heap.length > 0) {
            this.heap[0] = last;
            this._bubbleDown();
        }
        return min;
    }
    _bubbleUp() {
        let idx = this.heap.length - 1;
        while (idx > 0) {
            let parent = Math.floor((idx - 1) / 2);
            if (this.heap[parent] <= this.heap[idx]) break;
            [this.heap[parent], this.heap[idx]] = [this.heap[idx], this.heap[parent]];
            idx = parent;
        }
    }
    _bubbleDown() {
        let idx = 0, length = this.heap.length;
        while (true) {
            let left = 2 * idx + 1, right = 2 * idx + 2, swap = idx;
            if (left < length && this.heap[left] < this.heap[swap]) swap = left;
            if (right < length && this.heap[right] < this.heap[swap]) swap = right;
            if (swap === idx) break;
            [this.heap[idx], this.heap[swap]] = [this.heap[swap], this.heap[idx]];
            idx = swap;
        }
    }
    size() { return this.heap.length; }
}

class SeatManager {
    constructor(n) {
        this.available = new MinHeap();
        this.nextAvailable = 1;
        this.n = n;
    }
    reserve() {
        if (this.available.size() > 0) {
            return this.available.pop();
        }
        return this.nextAvailable++;
    }
    unreserve(seatNumber) {
        this.available.push(seatNumber);
    }
}