LeetCode 筆記 - 1845. Seat Reservation Manager

Posted on

題目在此 1845. Seat Reservation Manager

實作一個訂位系統，可以預約座位，並且可以釋放座位。

預約座位時，會從最小的座位開始預約。
釋放座位時，請將傳入的座位號碼加入到可用的座位中。image 106

預約時，保證還有可預約的座位；釋放時，保證傳入的座位號碼一定是已經預約過的。

解題思維

名詞解釋：

這題的重點在於，需要維護一個排序過的座位清單，才可以快速地找到最小的座位號碼。
如此一來，預約就變成是拿排序過後的座位清單的第一個元素；釋放就變成是將座位號碼加入到排序過後的座位清單中。

那將釋放的座位放進排序過後的座位清單中，這裡可以用 Binary Search 來快速地找到正確的位置。
那在 Python 中，有內建的 heapq 模組，可以幫助我們實作 Min Heap。

不過自己實作一次 Binary Search 也不錯，以下我提供兩種解法給各位同學。

這個解法是我自己實作的 Binary Search，可以參考一下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class SeatManager:

    def __init__(self, n: int):
        self.seats = [s + 1 for s in range(n)]
        
    def reserve(self) -> int:
        return self.seats.pop(0)

    def unreserve(self, seatNumber: int) -> None:
        size = len(self.seats)

        if size == 0:
            self.seats.append(seatNumber)
            return

        left = 0
        right = size - 1

        while left <= right:
            mid = (left + right) // 2

            if self.seats[mid] < seatNumber < self.seats[mid + 1]:
                self.seats.insert(mid + 1, seatNumber)
                return
            
            if seatNumber < self.seats[mid]:
                right = mid - 1
            elif self.seats[mid + 1] < seatNumber:
                left = mid + 1

        self.seats.insert(left, seatNumber)
image 1

解法 2: heapq

這個解法是使用 heapq 模組，可以參考一下。

1
2
3
4
5
6
7
8
9
10
11
class SeatManager:

    def __init__(self, n: int):
        self.seats = [s + 1 for s in range(n)]
        heapq.heapify(self.seats)

    def reserve(self) -> int:
        return heapq.heappop(self.seats)

    def unreserve(self, seatNumber: int) -> None:
        heapq.heappush(self.seats, seatNumber)
image 2

也許你也會想看看