⚡Flashcard Drill➔
NeetCode #540LC-1845MediumHeap / Priority Queue
← Back to All Problems

#540 · #1845 · Seat Reservation Manager(座位预约管理系统)

📌 Problem Statement & Constraints

Design a seat reservation manager for seats numbered 1..n. reserve() returns the smallest unreserved seat and marks it reserved; unreserve(seatNumber) frees it. Constraints: 1 <= n <= 10^5; at most 2 * 10^5 calls.

💡 Core Algorithmic Approaches

  1. A min-heap holding the currently free seat numbers gives the smallest seat in O(log n).
  2. reserve pops; unreserve pushes.
  3. Initialising the heap with all 1..n is O(n), which is fine given the constraints.
  4. An alternative avoids the initial O(n) by tracking the next never-used seat plus a heap of returned seats; that saves memory when few seats are used.

💻 Benchmark Python3 Implementation

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

    def reserve(self) -> int:
        import heapq
        return heapq.heappop(self.free)     # the smallest free seat

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


# Lazy variant: avoids materialising all n seats
class SeatManager2:
    def __init__(self, n: int):
        self.next_seat = 1                 # the smallest never-used seat
        self.returned = []                 # freed seats

    def reserve(self) -> int:
        import heapq
        if self.returned:
            return heapq.heappop(self.returned)   # prefer a recycled seat
        seat = self.next_seat
        self.next_seat += 1
        return seat

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

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(log n) per operation (O(n) for the constructor in the first variant).
💾 Space Complexity
O(n) for the heap; the lazy variant uses O(number of unreserved seats).

⚠️ Interview Pitfalls & Follow-ups

  • Using a sorted list with insertion: O(n) per unreserve due to shifting.
  • Scanning for the smallest free seat: O(n) per reserve.
  • Forgetting that a returned seat may be smaller than the next never-used one: the lazy variant must prefer the recycled seats.
  • Marking seats reserved with a boolean array only: finding the smallest free seat would be O(n).
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Heap / Priority Queue Problems