Sponsored
Sponsored
In this approach, we use a min-heap (priority queue) to efficiently manage and retrieve the smallest numbered unreserved seat.
SeatManager, we populate the heap with all seat numbers from 1 to n.reserve method, we simply extract the minimum element from the heap, which is the smallest numbered available seat.unreserve a seat, we add back the seat number to the heap, maintaining the heap properties.Time Complexity: O(log n) for both reserve and unreserve operations. We have to push and pop elements into/from a heap which takes logarithmic time.
Space Complexity: O(n) because of the storage required for the heap.
1import java.util.PriorityQueue;
2
3class SeatManager {
4 private PriorityQueue<Integer> availableSeats;
5
6 public SeatManager(int n) {
7 availableSeats = new PriorityQueue<>();
8 for (int i = 1; i <= n; i++) {
9 availableSeats.add(i);
10 }
11 }
12
13 public int reserve() {
14 return availableSeats.poll();
15 }
16
17 public void unreserve(int seatNumber) {
18 availableSeats.add(seatNumber);
19 }
20}The Java solution uses PriorityQueue to store available seat numbers. Initially, all seat numbers are added to the priority queue. The reserve method retrieves and removes the smallest element, and unreserve adds a seat number back using the add method.
Here, we use a data structure that maintains elements in sorted order, such as a TreeSet in Java and C# which keeps the seats sorted automatically.
reserve operation fetches and removes the first (smallest) element from the set.unreserve method, we simply add back the seat number to the set.Time Complexity: O(log n) for both reserve and unreserve operations because TreeSet operations like add, remove, and first take logarithmic time.
Space Complexity: O(n), as we store up to n seat numbers.
1import java.util.TreeSet;
The Java solution with TreeSet maintains a sorted set of available seats. The reserve method retrieves and removes the smallest element, while unreserve re-adds a seat number.