In this guide, you will get 1845. Seat Reservation Manager LeetCode Solution with the best time and space complexity. The solution to Seat Reservation Manager problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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.
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].
1 <= n <= 105
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 that seatNumber will be reserved.
At most 105 calls in total will be made to reserve and unreserve.
Complexity Analysis
Time Complexity: O(\log n)
Space Complexity: O(n)
1845. Seat Reservation Manager LeetCode Solution in C++
class SeatManager {
public:
SeatManager(int n) {}
int reserve() {
if (minHeap.empty())
return ++num;
const int minNum = minHeap.top();
minHeap.pop();
return minNum;
}
void unreserve(int seatNumber) {
minHeap.push(seatNumber);
}
private:
priority_queue<int, vector<int>, greater<>> minHeap;
int num = 0;
}; /* code provided by PROGIEZ */
1845. Seat Reservation Manager LeetCode Solution in Java
class SeatManager {
public SeatManager(int n) {}
public int reserve() {
if (minHeap.isEmpty())
return ++num;
return minHeap.poll();
}
public void unreserve(int seatNumber) {
minHeap.offer(seatNumber);
}
private Queue<Integer> minHeap = new PriorityQueue<>();
private int num = 0;
} // code provided by PROGIEZ
1845. Seat Reservation Manager LeetCode Solution in Python
class SeatManager:
def __init__(self, n: int):
self.minHeap = [i + 1 for i in range(n)]
def reserve(self) -> int:
return heapq.heappop(self.minHeap)
def unreserve(self, seatNumber: int) -> None:
heapq.heappush(self.minHeap, seatNumber) # code by PROGIEZ
