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 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 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#.