Seat Reservation Manager

medium heap design

Problem

Design a manager with reserve() (smallest unreserved) and unreserve(seat) operations.

Inputinit n=5; reserve, reserve, unreserve(2), reserve

Output[1,2,2]

Reserve→1; reserve→2; unreserve 2; reserve→2 again.

ops (R or U=k, semicolon)

import heapq
class SeatManager:
    def __init__(self, n):
        self.heap = list(range(1, n + 1))
    def reserve(self):
        return heapq.heappop(self.heap)
    def unreserve(self, seat):
        heapq.heappush(self.heap, seat)

class SeatManager {
  constructor(n) {
    this.h = [];
    for (let i = 1; i <= n; i++) this.h.push(i);
    // already sorted; use as binary heap (already valid since identity).
  }
  _swap(i, j) { [this.h[i], this.h[j]] = [this.h[j], this.h[i]]; }
  _up(i) { while (i > 0) { const p = (i - 1) >> 1; if (this.h[p] > this.h[i]) { this._swap(p, i); i = p; } else break; } }
  _down(i) { const n = this.h.length; for (;;) { const l = 2*i+1, r = 2*i+2; let m = i; if (l < n && this.h[l] < this.h[m]) m = l; if (r < n && this.h[r] < this.h[m]) m = r; if (m === i) return; this._swap(i, m); i = m; } }
  reserve() { const t = this.h[0]; const last = this.h.pop(); if (this.h.length) { this.h[0] = last; this._down(0); } return t; }
  unreserve(seat) { this.h.push(seat); this._up(this.h.length - 1); }
}

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

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

Explanation

The whole design rests on one simple idea: keep all the free seat numbers in a min-heap. A min-heap always gives back the smallest item instantly, which is exactly what reserve() needs.

In the constructor we fill the heap with seats 1 through n (all free at the start). Because they are added in order, the heap is already a valid min-heap.

To reserve(), we pop the heap, which removes and returns the smallest free seat. To unreserve(seat), we push that seat number back into the heap so it becomes available again, and the heap automatically keeps it in the right place.

Example: n = 5. First reserve() returns 1, second returns 2. Then unreserve(2) puts 2 back. The next reserve() pops the smallest free seat, which is 2 again.

Each operation is just one heap push or pop, so it stays fast at O(log n) even with many seats and many calls.

Time: O(log n) per op Space: O(n)