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
- A min-heap holding the currently free seat numbers gives the smallest seat in O(log n).
reservepops;unreservepushes.- Initialising the heap with all
1..nis O(n), which is fine given the constraints. - 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.