Problem
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 aSeatManager
object that will managen
seats numbered from1
ton
. 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 givenseatNumber
.
Examples
Example 1:
|
|
Solution
Method 1 – MinHeap with Lazy Initialization
Intuition
To efficiently manage seat reservations, we use a min-heap to keep track of seats that have been unreserved. Instead of initializing the heap with all seat numbers, we maintain a counter for the next available seat. This way, we only add seats to the heap when they are unreserved, saving both time and space.
Approach
- Use a min-heap to store seat numbers that have been unreserved.
- Maintain a counter to track the next seat to reserve.
- On reserve, return the smallest seat number from the heap if available; otherwise, use the counter and increment it.
- On unreserve, add the seat number back to the heap.
Complexity
- ⏰ Time complexity:
O(log n)
for reserve and unreserve due to heap operations. - 🧺 Space complexity:
O(n)
, for storing unreserved seat numbers in the heap.
Code
|
|
|
|
|
|