Seat Reservation Manager

Problem

SeatManager(n): n seats (1..n). reserve(): return smallest available. unreserve(seat): make available again.

Key insight: Min-heap. Initialize with [1..n]. reserve = pop min. unreserve = push back.

Solutions

# Python
import heapq

class SeatManager:
    def __init__(self, n):
        self.available = list(range(1, n + 1))
        heapq.heapify(self.available)

    def reserve(self):
        return heapq.heappop(self.available)

    def unreserve(self, seatNumber):
        heapq.heappush(self.available, seatNumber)

// C++
class SeatManager {
    priority_queue<int,vector<int>,greater<int>> minH;
public:
    SeatManager(int n) { for(int i=1;i<=n;i++) minH.push(i); }
    int reserve() { int s=minH.top(); minH.pop(); return s; }
    void unreserve(int s) { minH.push(s); }
};

// Java
class SeatManager {
    PriorityQueue<Integer> minH = new PriorityQueue<>();
    public SeatManager(int n) { for(int i=1;i<=n;i++) minH.offer(i); }
    public int reserve() { return minH.poll(); }
    public void unreserve(int seat) { minH.offer(seat); }
}

// JavaScript (sorted array)
class SeatManager {
    constructor(n) { this.seats = Array.from({length:n},(_,i)=>i+1); }
    reserve() { return this.seats.shift(); }
    unreserve(seat) {
        let pos = this.seats.findIndex(s => s > seat);
        if (pos === -1) this.seats.push(seat); else this.seats.splice(pos, 0, seat);
    }
}

Complexity

reserve/unreserve: O(log n)
Init: O(n) with heapify