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.
1using System.Collections.Generic;
2
3public 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 seatNumber = availableSeats.Min;
availableSeats.Remove(seatNumber);
return seatNumber;
}
public void Unreserve(int seatNumber) {
availableSeats.Add(seatNumber);
}
}The C# solution leverages SortedSet. It naturally keeps elements sorted, so the smallest seat can be selected with Min, and Remove and Add handle seat state changes efficiently.