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 heapq
2
3class SeatManager:
4 def __init__(self, n: int):
5 self.available_seats = list(range(1, n + 1))
6 heapq.heapify(self.available_seats)
7
8 def reserve(self) -> int:
9 return heapq.heappop(self.available_seats)
10
11 def unreserve(self, seatNumber: int) -> None:
12 heapq.heappush(self.available_seats, seatNumber)The Python solution uses the built-in heapq module to manage a min-heap representing the available seats. Initially, all seats are added to the heap. The reserve method pops the smallest item, while unreserve pushes a seat number back into the heap.
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.