# Seat Reservation Manager
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/seat-reservation-manager)
Canonical: https://scaleengineer.com/dsa/problems/seat-reservation-manager
**Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design)
**Data structures:** Heap (Priority Queue)
**Companies:** [Dropbox](https://scaleengineer.com/companies/dropbox), [Siemens](https://scaleengineer.com/companies/siemens)
---
## Problem
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 <= 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`.

# Approaches
## Brute Force using Boolean Array
This approach uses a boolean array to keep track of the status of each seat. A `true` value at an index indicates the seat is reserved, while `false` indicates it's available.
**Time:** - **Constructor**: O(n) to initialize the boolean array.
- **`reserve()`**: O(n) because in the worst case, we might have to scan the entire array to find an available seat.
- **`unreserve()`**: O(1) for direct array access. · **Space:** O(n) to store the state of `n` seats in the boolean array.
**Pros:** Simple to understand and implement.; `unreserve` is very fast, taking O(1) time.
**Cons:** The `reserve` operation is slow, with a time complexity of O(n). This can lead to a 'Time Limit Exceeded' error on platforms with strict time limits, especially given that n can be up to 10^5.
### Explanation
### Initialization
In the `SeatManager(n)` constructor, we create a boolean array `seats` of size `n + 1` (to accommodate 1-based indexing). We initialize all entries to `false`, signifying that all seats from 1 to `n` are initially available.

### `reserve()`
To reserve the smallest-numbered seat, we perform a linear scan through the `seats` array, starting from index 1. The first index `i` we find where `seats[i]` is `false` corresponds to the smallest available seat. We then mark this seat as reserved by setting `seats[i] = true` and return the seat number `i`.

### `unreserve(seatNumber)`
To unreserve a seat, we simply access the corresponding index in the array and set its value back to `false`. This is a constant-time operation.

```java
class SeatManager {
    private boolean[] reserved;
    private int n;

    public SeatManager(int n) {
        this.n = n;
        this.reserved = new boolean[n + 1]; // Using 1-based indexing
    }

    public int reserve() {
        for (int i = 1; i <= n; i++) {
            if (!reserved[i]) {
                reserved[i] = true;
                return i;
            }
        }
        return -1; // Should not happen based on problem constraints
    }

    public void unreserve(int seatNumber) {
        if (seatNumber >= 1 && seatNumber <= n) {
            reserved[seatNumber] = false;
        }
    }
}
```
### Algorithm
- `SeatManager(n)`:
  - Create a boolean array `reserved` of size `n+1`.
- `reserve()`:
  - Iterate `i` from 1 to `n`.
  - If `reserved[i]` is `false`:
    - Set `reserved[i]` to `true`.
    - Return `i`.
- `unreserve(seatNumber)`:
  - Set `reserved[seatNumber]` to `false`.

## Using a Min-Heap (PriorityQueue)
This approach maintains all available seats in a min-heap data structure. A min-heap is ideal because it always provides the smallest element (the smallest-numbered available seat) in logarithmic time.
**Time:** - **Constructor**: O(n log n) to add `n` elements to the priority queue. It can be optimized to O(n) by creating a list first and then initializing the priority queue from it.
- **`reserve()`**: O(log k), where `k` is the number of available seats. In the worst case, `k` can be `n`.
- **`unreserve()`**: O(log k). · **Space:** O(n) to store all `n` seat numbers in the priority queue at the beginning.
**Pros:** Significantly faster `reserve` operation compared to the linear scan approach.; Well-suited for the problem constraints.
**Cons:** Requires O(n) space from the start, which might be suboptimal if `n` is very large and the number of operations is small.; The constructor takes O(n log n) or O(n) time, which could be a factor in some scenarios.
### Explanation
### Initialization
In the `SeatManager(n)` constructor, we create a `PriorityQueue` (which acts as a min-heap in Java). We then populate it with all seat numbers from 1 to `n`. This ensures all seats are initially marked as available and are ordered by their number.

### `reserve()`
The `reserve` operation becomes very simple. The smallest-numbered available seat is always at the root of the min-heap. We can retrieve and remove it using the `poll()` method, which has a logarithmic time complexity.

### `unreserve(seatNumber)`
To unreserve a seat, we add its number back into the min-heap using the `add()` or `offer()` method. This operation also takes logarithmic time as the heap needs to maintain its property.

```java
import java.util.PriorityQueue;

class SeatManager {
    private PriorityQueue<Integer> availableSeats;

    public SeatManager(int n) {
        availableSeats = new PriorityQueue<>();
        for (int i = 1; i <= n; i++) {
            availableSeats.add(i);
        }
    }

    public int reserve() {
        return availableSeats.poll();
    }

    public void unreserve(int seatNumber) {
        availableSeats.add(seatNumber);
    }
}
```
### Algorithm
- `SeatManager(n)`:
  - Create a `PriorityQueue<Integer>` named `availableSeats`.
  - For `i` from 1 to `n`, add `i` to `availableSeats`.
- `reserve()`:
  - Call `availableSeats.poll()` and return the result.
- `unreserve(seatNumber)`:
  - Call `availableSeats.add(seatNumber)`.

## Optimized Min-Heap with a Counter
This is the most efficient approach. It leverages the fact that seats are initially reserved in increasing order (1, 2, 3, ...). We only need to use a data structure to manage the "gaps" created by `unreserve` operations.
**Time:** - **Constructor**: O(1).
- **`reserve()`**: O(log k), where `k` is the number of elements in the priority queue (i.e., the number of seats that have been unreserved).
- **`unreserve()`**: O(log k). · **Space:** O(k), where `k` is the maximum number of seats that are in the unreserved state at any given time. In the worst case, this is the total number of `unreserve` calls, which is bounded by 10^5. This is more space-efficient than the previous approaches if `n` is much larger than the number of calls.
**Pros:** Extremely fast O(1) constructor.; Optimal time complexity for `reserve` and `unreserve` operations.; Optimal space complexity, as it only stores what's necessary. The space used is proportional to the number of unreserved seats, not the total number of seats `n`.
**Cons:** Slightly more complex logic than the other approaches, but the benefits in performance are substantial.
### Explanation
### Data Structures
We use two main components:
1.  An integer counter, `nextAvailableSeat`, initialized to 1. This tracks the next seat to be given out from the contiguous block of unreserved seats.
2.  A min-heap (`PriorityQueue`), `unreservedSeats`, which is initially empty. This heap will store any seat numbers that are unreserved and are smaller than `nextAvailableSeat`.

### Initialization
The constructor is very lightweight. It just initializes `nextAvailableSeat` to 1 and creates an empty `PriorityQueue`.

### `reserve()`
When a reservation is requested, we first check if our `unreservedSeats` heap is empty.
- If it's not empty, it means there's a previously unreserved seat available that has a smaller number than our `nextAvailableSeat` counter. We `poll()` from the heap and return this seat number.
- If the heap is empty, it means there are no "gaps" to fill. The smallest available seat is the one pointed to by our counter. We return `nextAvailableSeat` and then increment it for the next call.

### `unreserve(seatNumber)`
When a seat is unreserved, we simply add its number to the `unreservedSeats` min-heap. This seat will then be available for a future `reserve()` call and will be prioritized by the heap if it's the smallest available.

```java
import java.util.PriorityQueue;

class SeatManager {
    private PriorityQueue<Integer> unreservedSeats;
    private int nextAvailableSeat;

    public SeatManager(int n) {
        // n is not strictly needed for this implementation but is part of the signature
        this.unreservedSeats = new PriorityQueue<>();
        this.nextAvailableSeat = 1;
    }

    public int reserve() {
        if (!unreservedSeats.isEmpty()) {
            return unreservedSeats.poll();
        }
        return nextAvailableSeat++;
    }

    public void unreserve(int seatNumber) {
        unreservedSeats.add(seatNumber);
    }
}
```
### Algorithm
- `SeatManager(n)`:
  - Initialize an integer `nextAvailableSeat = 1`.
  - Initialize an empty `PriorityQueue<Integer>` `unreservedSeats`.
- `reserve()`:
  - If `unreservedSeats` is not empty:
    - Return `unreservedSeats.poll()`.
  - Else:
    - Return `nextAvailableSeat++`.
- `unreserve(seatNumber)`:
  - Add `seatNumber` to `unreservedSeats`.

# Solutions
### CSharp

```csharp
public 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 reservedSeat = availableSeats . Min ; availableSeats . Remove ( reservedSeat ); return reservedSeat ; } public void Unreserve ( int seatNumber ) { availableSeats . Add ( seatNumber ); } } /** * Your SeatManager object will be instantiated and called as such: * SeatManager obj = new SeatManager(n); * int param_1 = obj.Reserve(); * obj.Unreserve(seatNumber); */
```

### Java

```java
class SeatManager { private PriorityQueue < Integer > q = new PriorityQueue <>(); public SeatManager ( int n ) { for ( int i = 1 ; i <= n ; ++ i ) { q . offer ( i ); } } public int reserve () { return q . poll (); } public void unreserve ( int seatNumber ) { q . offer ( seatNumber ); } } /** * Your SeatManager object will be instantiated and called as such: * SeatManager obj = new SeatManager(n); * int param_1 = obj.reserve(); * obj.unreserve(seatNumber); */
```

### Python

```python
class SeatManager : def __init__ ( self , n : int ): self . q = list ( range ( 1 , n + 1 )) heapify ( self . q ) def reserve ( self ) -> int : return heappop ( self . q ) def unreserve ( self , seatNumber : int ) -> None : heappush ( self . q , seatNumber ) # Your SeatManager object will be instantiated and called as such: # obj = SeatManager(n) # param_1 = obj.reserve() # obj.unreserve(seatNumber)
```

### CPP

```cpp
class SeatManager { public: SeatManager ( int n ) { for ( int i = 1 ; i <= n ; ++ i ) { q . push ( i ); } } int reserve () { int seat = q . top (); q . pop (); return seat ; } void unreserve ( int seatNumber ) { q . push ( seatNumber ); } private: priority_queue < int , vector < int > , greater < int >> q ; }; /** * Your SeatManager object will be instantiated and called as such: * SeatManager* obj = new SeatManager(n); * int param_1 = obj->reserve(); * obj->unreserve(seatNumber); */
```