Formatted question description: https://leetcode.ca/all/1845.html

# 1845. Seat Reservation Manager

## Level

Medium

## Description

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 <= 10^5`

`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
`10^5`

calls**in total**will be made to`reserve`

and`unreserve`

.

## Solution

Maintain `curr`

to store the seat to be reserved. Use a tree set to store unreserved seats.

For the constructor, initialize `curr = 1`

and initialize the tree set.

For `reserve`

, if the tree set is not empty, then use the smallest element in the tree set as the reserved seat and remove it from the tree set. Otherwise, use `curr`

as the reserved seat and increase `curr`

by 1.

For `unreserve`

, add `seatNumber`

to the tree set.

```
class SeatManager {
int n;
int curr;
TreeSet<Integer> set;
public SeatManager(int n) {
this.n = n;
curr = 1;
set = new TreeSet<Integer>();
}
public int reserve() {
if (!set.isEmpty()) {
int reserveSeat = set.first();
set.remove(reserveSeat);
return reserveSeat;
} else {
int reserveSeat = curr;
curr++;
return reserveSeat;
}
}
public void unreserve(int seatNumber) {
set.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);
*/
```