Seat Reservation Manager
Medium · Heap & Counting · Design · Heap (Priority Queue)
Problem
Design a class that manages reservations for n seats numbered 1 to n.
Implement SeatManager:
- SeatManager(n) sets up n seats, all free at first.
- reserve() reserves the lowest-numbered free seat and returns its number.
- unreserve(seatNumber) makes that seat free again.
Tests replay a call sequence: the first entry names the class and its constructor arguments, each later entry is a method with its arguments, and each call reports its return value (None for the constructor and for unreserve).
Examples
Input: ops = ["SeatManager","reserve","reserve","reserve","unreserve","reserve","reserve"], args = [[4],[],[],[],[1],[],[]] Output: [None, 1, 2, 3, None, 1, 4]
Seats 1 to 3 are handed out, seat 1 is given back and handed out again, and then seat 4 is the lowest free seat.
Input: ops = ["SeatManager","reserve","unreserve","reserve"], args = [[1],[],[1],[]] Output: [None, 1, None, 1]
The only seat is reserved, freed and reserved again.
Input: ops = ["SeatManager","reserve","reserve","reserve","unreserve","unreserve","reserve","reserve"], args = [[5],[],[],[],[3],[2],[],[]] Output: [None, 1, 2, 3, None, None, 2, 3]
Seats 3 and 2 are given back; the next two reserves return them lowest first, 2 then 3.
Constraints
- 1 <= n <= 10^5
- 1 <= seatNumber <= n
- reserve is called only when at least one seat is free
- unreserve is called only on a reserved seat
- At most 10^5 calls to reserve and unreserve in total
Approaches
- Min-heap of all free seats — time O(log n) per call, O(n) setup, space O(n)
Follow-up
If customers could also ask for a specific seat, that seat would have to leave the middle of the heap. Instead of searching for it, mark it as taken and skip it when it reaches the top (lazy deletion). If you also had to report the highest free seat, an ordered set (TreeSet, std::set, sortedcontainers) gives both ends in O(log n).
Related problems
Start free on Cariara · Coding problems · System design studio
