Watch 10 video solutions for Seat Reservation Manager, a medium level problem involving Design, Heap (Priority Queue). This walkthrough by NeetCode has 9,535 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Design a system that manages the reservation state of n seats that are numbered from 1 to n.
Implement the SeatManager class:
SeatManager(int n) Initializes a SeatManager object that will manage n seats numbered from 1 to n. All seats are initially available.int reserve() Fetches the smallest-numbered unreserved seat, reserves it, and returns its number.void unreserve(int seatNumber) Unreserves the seat with the given seatNumber.
Example 1:
Input ["SeatManager", "reserve", "reserve", "unreserve", "reserve", "reserve", "reserve", "reserve", "unreserve"] [[5], [], [], [2], [], [], [], [], [5]] Output [null, 1, 2, null, 2, 3, 4, 5, null] Explanation SeatManager seatManager = new SeatManager(5); // Initializes a SeatManager with 5 seats. seatManager.reserve(); // All seats are available, so return the lowest numbered seat, which is 1. seatManager.reserve(); // The available seats are [2,3,4,5], so return the lowest of them, which is 2. seatManager.unreserve(2); // Unreserve seat 2, so now the available seats are [2,3,4,5]. seatManager.reserve(); // The available seats are [2,3,4,5], so return the lowest of them, which is 2. seatManager.reserve(); // The available seats are [3,4,5], so return the lowest of them, which is 3. seatManager.reserve(); // The available seats are [4,5], so return the lowest of them, which is 4. seatManager.reserve(); // The only available seat is seat 5, so return 5. seatManager.unreserve(5); // Unreserve seat 5, so now the available seats are [5].
Constraints:
1 <= n <= 1051 <= seatNumber <= nreserve, it is guaranteed that there will be at least one unreserved seat.unreserve, it is guaranteed that seatNumber will be reserved.105 calls in total will be made to reserve and unreserve.Problem Overview: You need to design a seat reservation system that always assigns the smallest available seat number. Two operations exist: reserve() returns the lowest-numbered free seat, and unreserve(seatNumber) makes a seat available again. The challenge is maintaining the smallest free seat efficiently as seats are reserved and returned.
Approach 1: Min-Heap for Available Seats (O(log n) per operation)
The most common solution uses a min-heap (priority queue) to track all currently available seat numbers. Initially, push all seats from 1 to n into the heap. When reserve() is called, remove the smallest element using heappop() or poll(), which guarantees the lowest-numbered seat. When unreserve(seatNumber) is called, push that seat number back into the heap so it becomes available again. Each heap push or pop costs O(log n) time and the heap stores up to O(n) elements. This approach works well because heaps are optimized for repeatedly extracting the smallest value.
Approach 2: TreeSet (Sorted Set) to Track Free Seats (O(log n) per operation)
A TreeSet or other balanced binary search tree can maintain seat numbers in sorted order. Insert all seat numbers from 1 to n into the set during initialization. The reserve() operation retrieves and removes the smallest element using first() and remove(). When unreserve(seatNumber) is called, insert that seat number back into the set. Because a TreeSet is backed by a self-balancing BST, both insertion and deletion take O(log n) time while maintaining sorted order. Space complexity is O(n). This method is clean and idiomatic in languages like Java or C# where sorted sets are built-in.
Both approaches fall under the design category because you are implementing a data structure with defined operations and performance guarantees. The key observation is that the smallest available seat must always be accessible quickly. Using either a heap or a balanced ordered set ensures that retrieving the minimum value remains efficient even as seats are returned to the pool.
Recommended for interviews: The min-heap solution is usually expected. It directly models the requirement of always retrieving the smallest available seat and keeps the implementation simple. The TreeSet solution demonstrates familiarity with ordered sets and balanced trees, which is useful in languages with strong standard libraries. Showing both approaches signals strong understanding of priority queues and ordered data structures.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Min-Heap (Priority Queue) | O(log n) per reserve/unreserve | O(n) | Best general solution when you need constant access to the smallest available seat |
| TreeSet / Sorted Set | O(log n) per operation | O(n) | Ideal in languages with built-in ordered sets like Java or C# |