實作餐廳訂位報號系統 Seat Reservation Manager Leetcode #1845

這題的題目在這裡:

題目敘述

題目會定義一組類別和介面，要求我們實做餐廳訂位報號系統。

SeatManager(int n) : 初始化餐廳最多有n個座位，n 最少是1

int reserve() : 要求返回最小的可讓客人入座的空座位編號。

void unreserve(int 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 10^5 calls in total will be made to reserve and unreserve.

演算法

題目已經給定座位號碼都是１～ｎ的整數。

而且，剛好要求返回的帶位號碼是要求從當下最小的空位開始帶位。

很直覺的，可以想到用min Heap 最小堆積　搭配　當前最後一筆帶位號碼last_seat_num來實作整個餐廳訂位系統。

報空位帶位時，假如min Heap非空，代表有之前退還回來的空位，則從min Heap取出最小的空位號碼。

假如min Heap為空，代表沒有之前退還回來的空位。直接從１，２，３．．．的順序，從小到大回報空位即可，並且，把空位記錄在last_seat_num。

取消訂位時，假如取消的座位和last_seat_num相同，代表是取消剛剛近來的那筆最新的定位，這時侯，只要在last_seat_num減一，做取消訂位即可。

假如取消的座位和last_seat_num不同，代表是取消的很久以前的訂位，這時候就把取消的座位號碼推入min Heap 被退回空位的池子裡（本身用最小堆積來實作，保證之後取到的都是從小的號碼開始取）。

程式碼

class SeatManager:

　def __init__(self, n: int):

　　# Build a minheap
　　self.min_heap = []
　　self.last_seat_num = 0

　def reserve(self) -> int:
　　# pop out smallest number
　　if self.min_heap:
　　　cur = heapq.heappop(self.min_heap)
　　　return cur
　　
　　else:
　　　self.last_seat_num += 1
　　　return self.last_seat_num
　　

　def unreserve(self, seatNumber: int) -> None:
　　if self.last_seat_num == seatNumber:
　　　self.last_seat_num -= 1
　　　
　　else:
　　　# push unreserved number back to minheap
　　　heapq.heappush(self.min_heap, seatNumber)
　　return


# Your SeatManager object will be instantiated and called as such:
# obj = SeatManager(n)
# param_1 = obj.reserve()
# obj.unreserve(seatNumber)​

複雜度分析

時間複雜度:

init(): O(1)

reserve(): O( log n ) min heap 取出頂端的最小值，並且調整min heap。

unreseve(): O( log n ) min heap 推入被退回的空位，並且調整min heap。

空間複雜度: O(ｎ)
當全部訂位訂滿之後，從一號開始連續退回空位時，min heap所佔用空間有可能到達最大座位號碼Ｏ（n）

關鍵知識點

從餐廳帶位總是從最小號碼開始帶位，聯想到使用ｍｉｎ　ｈｅａｐ最小堆積來實作。

Reference:

[1] Seat Reservation Manager - LeetCode