648. Seat Reservation Manager
Design a SeatManager that hands out seats in a venue with n seats labeled 1 through n. Every seat starts out available.
Implement three operations:
SeatManager(n)— initialize the manager fornseats.reserve()— take the lowest-numbered seat that is still available, mark it reserved, and return its number.unreserve(seatNumber)— release seatseatNumberso it becomes available again.
Your program receives n followed by a sequence of operations and must print the seat number returned by every reserve call, one per line, in the order the calls happen.
Example 1:
Input: SeatManager(3); reserve(), reserve(), unreserve(1), reserve(), reserve()
Output: 1, 2, 1, 3
Explanation: The first two reserves hand out seats 1 and 2. After seat 1 is released, the next reserve returns 1 again (it is the smallest available), and the last reserve returns 3.
Example 2:
Input: SeatManager(5); reserve() ×3, unreserve(2), unreserve(1), reserve() ×3
Output: 1, 2, 3, 1, 2, 4
Explanation: Seats 1, 2, 3 go out first. Releasing 2 and then 1 makes both available again, so the following reserves return 1, then 2, then the fresh seat 4.
Constraints:
- 1 ≤ n ≤ 10⁵
- 1 ≤ seatNumber ≤ n
- At most 10⁵ operations in total.
- unreserve is only ever called on a seat that is currently reserved.
- reserve is only ever called while at least one seat is available.
Hints:
Scanning seats 1..n on every reserve works but costs O(n) per call. You need a structure that can report and remove the minimum quickly.
Released seats arrive in arbitrary order — keep them in a min-heap. Seats that were never handed out don't need to be stored at all: they are exactly the contiguous block starting at a counter.
reserve: if the heap of released seats is non-empty, pop it; otherwise return the counter and bump it. Any released seat is always smaller than any never-used seat, so this order is safe.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: SeatManager(3); reserve(), reserve(), unreserve(1), reserve(), reserve()
Expected output: 1, 2, 1, 3