推 wwndbk: 大師 11/06 17:12
推 oin1104: 大師 11/06 17:14
※ 引述《ZooseWu (動物園 公告)》之銘言：
: 1845. Seat Reservation Manager
: 設計一個訂位系統。
: 1.初始化，它會給你一個n代表有n個位子可以訂，初始時所有位置都是可訂狀態。
: 2.reserve() 選擇可訂位中數字最小的一個位子並回傳。
: 3.unreserve(int seatNumber) 取消數字seatNumber的訂位。
思路：
1.初始情況 1~n 都可以預約，然後數字小的會先被預約，就是一直取一個一直遞增的
值（假設為id）。
2.會發生變化只有前面預約的人取消了預約，因為被取消的編號一定比當前id小。
我們把這些取消的座位編號排序放到一個容器，如果容器不為空就從容器裡面取
最小值，否則繼續取當前id，容器方面選用 heap 就可以實現取消的位子自動排序。
Java Code：
----------------------------------------------------------
class SeatManager {
private PriorityQueue<Integer> heap;
private int id;
public SeatManager(int n) {
heap = new PriorityQueue<>();
id = 1;
}
public int reserve() {
if (!heap.isEmpty()) {
return heap.poll();
} else {
return id++;
}
}
public void unreserve(int seatNumber) {
heap.offer(seatNumber);
}
}
----------------------------------------------------------
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.73.13 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1699261533.A.13C.html