Welcome to Subscribe On Youtube
1845. Seat Reservation Manager
Description
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 smallestnumbered unreserved seat, reserves it, and returns its number.void unreserve(int seatNumber)
Unreserves the seat with the givenseatNumber
.
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 <= 10^{5}
1 <= seatNumber <= n
 For each call to
reserve
, it is guaranteed that there will be at least one unreserved seat.  For each call to
unreserve
, it is guaranteed thatseatNumber
will be reserved.  At most
10^{5}
calls in total will be made toreserve
andunreserve
.
Solutions
Solution 1: Priority Queue (Min Heap)
We can use a priority queue (min heap) to maintain the smallest number of reservable seats.
Initially, put all seat numbers into the priority queue.
When the reserve
method is called, take out the smallest number from the priority queue, which is the smallest number of reservable seats.
When the unreserve
method is called, put the seat number back into the priority queue.
The time complexity is $O(n \times \log n)$, and the space complexity is $O(n)$. Where $n$ is the number of seats.

class SeatManager { private PriorityQueue<Integer> q = new PriorityQueue<>(); public SeatManager(int n) { for (int i = 1; i <= n; ++i) { q.offer(i); } } public int reserve() { return q.poll(); } public void unreserve(int seatNumber) { q.offer(seatNumber); } } /** * Your SeatManager object will be instantiated and called as such: * SeatManager obj = new SeatManager(n); * int param_1 = obj.reserve(); * obj.unreserve(seatNumber); */

class SeatManager { public: SeatManager(int n) { for (int i = 1; i <= n; ++i) { q.push(i); } } int reserve() { int seat = q.top(); q.pop(); return seat; } void unreserve(int seatNumber) { q.push(seatNumber); } private: priority_queue<int, vector<int>, greater<int>> q; }; /** * Your SeatManager object will be instantiated and called as such: * SeatManager* obj = new SeatManager(n); * int param_1 = obj>reserve(); * obj>unreserve(seatNumber); */

class SeatManager: def __init__(self, n: int): self.q = list(range(1, n + 1)) heapify(self.q) def reserve(self) > int: return heappop(self.q) def unreserve(self, seatNumber: int) > None: heappush(self.q, seatNumber) # Your SeatManager object will be instantiated and called as such: # obj = SeatManager(n) # param_1 = obj.reserve() # obj.unreserve(seatNumber)

type SeatManager struct { q hp } func Constructor(n int) SeatManager { q := hp{} for i := 1; i <= n; i++ { heap.Push(&q, i) } return SeatManager{q} } func (this *SeatManager) Reserve() int { return heap.Pop(&this.q).(int) } func (this *SeatManager) Unreserve(seatNumber int) { heap.Push(&this.q, seatNumber) } type hp struct{ sort.IntSlice } func (h hp) Less(i, j int) bool { return h.IntSlice[i] < h.IntSlice[j] } func (h *hp) Push(v any) { h.IntSlice = append(h.IntSlice, v.(int)) } func (h *hp) Pop() any { a := h.IntSlice v := a[len(a)1] h.IntSlice = a[:len(a)1] return v } /** * Your SeatManager object will be instantiated and called as such: * obj := Constructor(n); * param_1 := obj.Reserve(); * obj.Unreserve(seatNumber); */

public class SeatManager { private SortedSet<int> availableSeats; public SeatManager(int n) { availableSeats = new SortedSet<int>(); for (int i = 1; i <= n; i++) { availableSeats.Add(i); } } public int Reserve() { int reservedSeat = availableSeats.Min; availableSeats.Remove(reservedSeat); return reservedSeat; } public void Unreserve(int seatNumber) { availableSeats.Add(seatNumber); } } /** * Your SeatManager object will be instantiated and called as such: * SeatManager obj = new SeatManager(n); * int param_1 = obj.Reserve(); * obj.Unreserve(seatNumber); */