Leetcode 1845. Seat Reservation Manager
Problem Explanation
We want to design a reservation system for a set of n
seats. All seats are numbered from 1 to n
and initially, all of them are unreserved. Our task is to implement the SeatManager
class which has the following methods:
-
SeatManager(int n)
: Initializes a SeatManager object that will managen
seats numbered from 1 ton
. All seats are initially available. -
int reserve()
: Fetches the smallest-numbered unreserved seat, reserves it, and returns the seat number. -
void unreserve(int seatNumber)
: Unreserves the seat with the given seat number.
Approach
We can solve this problem using a priority queue (Min Heap) data structure. The Min Heap will help us to automatically sort the available unreserved seats by their seat numbers, where the smallest priority is the smallest seat number.
Initially, the Min Heap is empty, and we have a counter num
set to 0, to keep track of the reserved seats.
For the reserve
function, if the Min Heap is empty, it means all seats are reserved in ascending order till num
. Therefore, the smallest unreserved seat is (num + 1)
. So, we increment num
and return it as the next reserved seat number. Otherwise, we get the highest priority seat number (lowest seat number) from the Min Heap, reserve it by removing it from the Min Heap, and return its number.
For the unreserve
function, we insert the seat number back into the Min Heap.
Example
Let's walk through an example to demonstrate the steps:
SeatManager seatManager = new SeatManager(5); // Initializes a SeatManager with 5 seats. seatManager.reserve(); // minHeap is empty, num = 0. Reserve seat 1, increment num to 1 and return 1. seatManager.reserve(); // minHeap is empty, num = 1. Reserve seat 2, increment num to 2 and return 2. seatManager.unreserve(2); // Unreserve seat 2, so now the minHeap contains 2, available seats are [2, 3, 4, 5]. seatManager.reserve(); // minHeap contains 2, remove 2 from minHeap, and return it. So reserved seat is 2. seatManager.reserve(); // minHeap is empty, num = 2. Reserve seat 3, increment num to 3 and return 3. seatManager.reserve(); // minHeap is empty, num = 3. Reserve seat 4, increment num to 4 and return 4. seatManager.reserve(); // minHeap is empty, num = 4. Reserve seat 5, increment num to 5 and return 5. seatManager.unreserve(5); // Unreserve seat 5, so now the minHeap contains 5, available seats are [5].
Solution in Python
1import heapq
2
3class SeatManager:
4 def __init__(self, n: int):
5 self.minHeap = []
6 self.num = 0
7
8 def reserve(self) -> int:
9 if not self.minHeap:
10 self.num += 1
11 return self.num
12
13 min_num = heapq.heappop(self.minHeap)
14 return min_num
15
16 def unreserve(self, seatNumber: int) -> None:
17 heapq.heappush(self.minHeap, seatNumber)
Solution in Java
1import java.util.PriorityQueue;
2
3class SeatManager {
4 private PriorityQueue<Integer> minHeap;
5 private int num;
6
7 public SeatManager(int n) {
8 minHeap = new PriorityQueue<>();
9 num = 0;
10 }
11
12 public int reserve() {
13 if (minHeap.isEmpty()) {
14 num++;
15 return num;
16 }
17
18 int minNum = minHeap.poll();
19 return minNum;
20 }
21
22 public void unreserve(int seatNumber) {
23 minHeap.offer(seatNumber);
24 }
25}
Solution in JavaScript
1class SeatManager {
2 constructor(n) {
3 this.minHeap = new PriorityQueue();
4 this.num = 0;
5 }
6
7 reserve() {
8 if (this.minHeap.isEmpty()) {
9 this.num++;
10 return this.num;
11 }
12
13 const minNum = this.minHeap.pop();
14 return minNum;
15 }
16
17 unreserve(seatNumber) {
18 this.minHeap.push(seatNumber);
19 }
20}
Solution in C++
1#include <queue>
2
3class SeatManager {
4public:
5 SeatManager(int n) {
6
7 }
8
9 int reserve() {
10 if (minHeap.empty()) {
11 num++;
12 return num;
13 }
14
15 int minNum = minHeap.top();
16 minHeap.pop();
17 return minNum;
18 }
19
20 void unreserve(int seatNumber) {
21 minHeap.push(seatNumber);
22 }
23
24private:
25 std::priority_queue<int, std::vector<int>, std::greater<> > minHeap;
26 int num = 0;
27};
Solution in C#
1using System.Collections.Generic;
2
3public class SeatManager {
4 private SortedSet<int> minHeap;
5 private int num;
6
7 public SeatManager(int n) {
8 minHeap = new SortedSet<int>();
9 num = 0;
10 }
11
12 public int Reserve() {
13 if (minHeap.Count == 0) {
14 num++;
15 return num;
16 }
17
18 int minNum = minHeap.Min;
19 minHeap.Remove(minNum);
20 return minNum;
21 }
22
23 public void Unreserve(int seatNumber) {
24 minHeap.Add(seatNumber);
25 }
26}
27```## Wrapping Up
28
29In this article, we learned how to design a seat reservation system using a priority queue (Min Heap) data structure. The Min Heap allowed us to find the smallest unreserved seat number easily for each `reserve` operation. We then implemented the required `SeaManager`, `reserve`, and `unreserve` functions in multiple programming languages, including Python, Java, JavaScript, C++, and C#.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.