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.
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 <= 1051 <= seatNumber <= nreserve, it is guaranteed that there will be at least one unreserved seat.unreserve, it is guaranteed that seatNumber will be reserved.105 calls in total will be made to reserve and unreserve.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.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.
Java
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.
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.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.
C#
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.
| Approach | Complexity |
|---|---|
| Using a Min-Heap to Manage Seats | Time Complexity: Space Complexity: |
| Using a TreeSet (Sorted Set) to Manage Seats | Time Complexity: Space Complexity: |
Seat Reservation Manager - Leetcode 1845 - Python • NeetCode • 8,764 views views
Watch 9 more video solutions →Practice Seat Reservation Manager with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor