題目在此 1845. Seat Reservation Manager
實作一個訂位系統,可以預約座位,並且可以釋放座位。
預約座位時,會從最小的座位開始預約。
釋放座位時,請將傳入的座位號碼加入到可用的座位中。
預約時,保證還有可預約的座位;釋放時,保證傳入的座位號碼一定是已經預約過的。
解題思維
名詞解釋:
這題的重點在於,需要維護一個排序過的座位清單,才可以快速地找到最小的座位號碼。
如此一來,預約就變成是拿排序過後的座位清單的第一個元素;釋放就變成是將座位號碼加入到排序過後的座位清單中。
那將釋放的座位放進排序過後的座位清單中,這裡可以用 Binary Search 來快速地找到正確的位置。
那在 Python 中,有內建的 heapq 模組,可以幫助我們實作 Min Heap。
不過自己實作一次 Binary Search 也不錯,以下我提供兩種解法給各位同學。
解法 1: 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)
|
解法 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)
|
相關文章