Seat Reservation Manager — Min-Heap for Dynamic Availability Tracking

Problem Statement#

Design a system that manages the reservation state of n seats numbered 1 through n:

• SeatManager(n) — initialize with seats 1 to n, all unreserved.
• reserve() — return the smallest-numbered unreserved seat and mark it reserved.
• unreserve(seatNumber) — mark seatNumber as unreserved.

Constraints:

• 1 <= n <= 10^5
• 1 <= seatNumber <= n
• For each call to reserve, it is guaranteed that there is at least one unreserved seat.
• For each call to unreserve, it is guaranteed that seatNumber is currently reserved.
• At most 10^5 calls total to reserve and unreserve.

Examples:

Input:
["SeatManager", "reserve", "reserve", "unreserve", "reserve", "reserve", "reserve", "reserve", "unreserve"]
[[5], [], [], [2], [], [], [], [], [5]]
 
Output:
[null, 1, 2, null, 2, 3, 4, 5, null]

Why This Problem Matters#

Seat Reservation Manager is a clean medium problem that perfectly illustrates the power of the min-heap for priority-ordered resource management. It's a favorite warm-up problem at Amazon and Microsoft because it directly maps to real systems they build: ticket booking systems, database connection pool managers, thread pool schedulers, and parking lot management systems.

The problem tests whether candidates know to use a min-heap (O(log n) per operation) rather than a sorted set (O(log n)) or a linear scan (O(n)). The heap solution is simple and elegant — often just 5-10 lines of code — but candidates who aren't familiar with heaps often default to a slow linear scan or an incorrect set-based approach.

This problem is also a great starter for discussing lazy initialization: instead of pushing all n seats into the heap upfront (O(n) space and time), you could track the "next available sequential seat" with a pointer and only push seats into the heap when they're unreserved. This optimization reduces initialization to O(1) when few seats are unreserved at any time.

Understanding this problem helps you immediately recognize and solve "Seat Manager" variants in system design interviews: "Design a parking lot," "Design a library book management system," and "Design a connection pool" all have the same core data structure pattern.

The Core Insight#

The insight is straightforward: a min-heap is the perfect data structure for this problem because:

1. reserve() always needs the minimum available seat → min-heap gives O(log n) pop.
2. unreserve(seat) puts a seat back into the pool → min-heap gives O(log n) push.
3. The heap automatically maintains the smallest element at the top.

No sorting, no linear scan, no complex data structure. Just a min-heap.

Optimization — lazy initialization: Instead of pushing 1 through n into the heap upfront, maintain a pointer next_seat starting at 1. When reserving:

• If the heap is non-empty and its top ≤ next_seat, use the heap (handles unreserved seats).
• Otherwise, use next_seat and advance it.

This reduces initialization to O(1) and avoids allocating O(n) memory for the heap when n is large and few operations are performed.

Visual Dry Run#

n=5, operations: reserve, reserve, unreserve(2), reserve, reserve, reserve
 
Initial heap: [1, 2, 3, 4, 5]
 
reserve() → pop 1. heap=[2,3,4,5]. Return 1.
reserve() → pop 2. heap=[3,4,5]. Return 2.
unreserve(2) → push 2. heap=[2,3,4,5].
reserve() → pop 2. heap=[3,4,5]. Return 2.
reserve() → pop 3. heap=[4,5]. Return 3.
reserve() → pop 4. heap=[5]. Return 4.
reserve() → pop 5. heap=[]. Return 5.
unreserve(5) → push 5. heap=[5].

Solution (Optimal)#

import heapq
 
class SeatManager:
    def __init__(self, n: int):
        # Initialize all seats as available in a min-heap
        self.available = list(range(1, n + 1))
        heapq.heapify(self.available)
        # O(n) initialization. For lazy init: self.next = 1; self.available = []
    
    def reserve(self) -> int:
        return heapq.heappop(self.available)
    
    def unreserve(self, seatNumber: int) -> None:
        heapq.heappush(self.available, seatNumber)

class SeatManager {
    constructor(n) {
        // For simplicity, initialize with all seats sorted
        // In production, use a proper binary heap library
        this.available = Array.from({ length: n }, (_, i) => i + 1);
        // Already in sorted order (min-heap property satisfied for sorted array)
        this.heapSize = n;
        this._buildHeap();
    }
    
    _buildHeap() {
        // No-op since array is already sorted (min-heap property holds trivially)
        // For a general array, we'd sift-down from n/2 to 0
    }
    
    _siftUp(i) {
        while (i > 0) {
            const parent = (i - 1) >> 1;
            if (this.available[parent] > this.available[i]) {
                [this.available[parent], this.available[i]] = [this.available[i], this.available[parent]];
                i = parent;
            } else break;
        }
    }
    
    _siftDown(i) {
        const n = this.heapSize;
        while (true) {
            let smallest = i;
            const l = 2 * i + 1, r = 2 * i + 2;
            if (l < n && this.available[l] < this.available[smallest]) smallest = l;
            if (r < n && this.available[r] < this.available[smallest]) smallest = r;
            if (smallest === i) break;
            [this.available[i], this.available[smallest]] = [this.available[smallest], this.available[i]];
            i = smallest;
        }
    }
    
    reserve() {
        const seat = this.available[0];
        this.heapSize--;
        this.available[0] = this.available[this.heapSize];
        this._siftDown(0);
        return seat;
    }
    
    unreserve(seatNumber) {
        this.available[this.heapSize] = seatNumber;
        this.heapSize++;
        this._siftUp(this.heapSize - 1);
    }
}

Complexity Analysis:

• SeatManager(n): O(n) — building heap from array
• reserve(): O(log n) — heap pop
• unreserve(seat): O(log n) — heap push
• Space: O(n) — heap stores all n seats

Lazy initialization alternative:

class SeatManagerLazy:
    def __init__(self, n):
        self.available = []  # Only holds unreserved seats that aren't in sequence
        self.next_seq = 1    # Next sequential seat not yet touched
        self.n = n
    
    def reserve(self):
        if self.available and self.available[0] < self.next_seq:
            return heapq.heappop(self.available)
        seat = self.next_seq
        self.next_seq += 1
        return seat
    
    def unreserve(self, seat):
        heapq.heappush(self.available, seat)

Common Mistakes#

• Using a set and finding the minimum manually. Sets don't support O(1) minimum finding; you'd need min(set) which is O(n). Use a heap.
• Not using heapq.heapify for initialization. Pushing elements one by one into a heap is O(n log n). Building from a list with heapify is O(n).
• Forgetting that Python's heapq is a min-heap. No configuration needed — it naturally gives the smallest element first, which is exactly what reserve() needs.
• Returning the seat number without marking it reserved. In some implementations, you need to track reserved seats separately if unreserve validation is required.
• Off-by-one: seats numbered 1 to n, not 0 to n-1. Initialize with range(1, n+1).

Follow-up Questions#

1. Implement the lazy initialization variant. When does it outperform the eager initialization?
2. What if unreserve could be called with an already-unreserved seat (invalid call)? How would you validate?
3. What if you need both reserveMin() and reserveMax() — reserve the smallest or largest seat on demand? (Hint: Use both a min-heap and a max-heap.)
4. What if seats have priorities and you always reserve the highest-priority available seat? Generalize the heap comparator.
5. Design a parking lot where spots have types (compact, standard, large) and vehicles prefer the smallest matching spot. How many heaps do you need?
6. What is the time complexity if you use a sorted set (e.g., SortedList in Python) instead of a heap? Same asymptotic, but different constants.

Key Takeaways#

• A min-heap of available seat numbers gives O(log n) reserve (pop min) and O(log n) unreserve (push back) — far better than O(n) linear scan.
• Initialize with heapq.heapify(list(range(1, n+1))) in O(n) — faster than n individual pushes which cost O(n log n).
• Lazy initialization alternative: track a sequential pointer and only push to the heap when seats are unreserved — reduces init to O(1) when few unreservations happen.
• Python's heapq is a min-heap natively; no configuration needed. Seats numbered 1 to n, so initialize with range(1, n+1).
• This heap-for-resource-pool pattern appears in parking lots, connection pools, thread schedulers, and ticket booking systems — always mention real-world analogies in interviews.
• Amazon and Microsoft use this as a warm-up problem to quickly verify heap fluency before moving to harder design questions.
• For a variant requiring both smallest and largest seat: use two heaps (min and max) with a shared reserved set to keep them synchronized.