Description
設計一個座位預約管理系統。系統管理從 1 到 n 編號的座位。實作
SeatManager類別：SeatManager(int n)初始化，reserve()預約並回傳最小編號的未預約座位，unreserve(int seatNumber)取消預約。
Example:
Input: [“SeatManager”, “reserve”, “reserve”, “unreserve”, “reserve”, “reserve”, “reserve”, “reserve”, “unreserve”] [[5], [], [], [2], [], [], [], [], [5]] Output: [null, 1, 2, null, 2, 3, 4, 5, null]
Intuition#
核心思路：用 Min Heap 維護所有可用座位，reserve 取堆頂，unreserve 加回 heap。
- 每次需要最小編號的座位 → 天然適合 Min Heap
- 初始化時不必一次加入所有座位，可以用一個計數器延遲加入
- unreserve 的座位直接加回 heap 即可
Approaches#
1: Min Heap（全部預載）#
- 概念: 初始化時將 1 到 n 全部加入 Min Heap
- 時間複雜度: 初始化
O(n)，reserve/unreserveO(log n) - 空間複雜度:
O(n)
class SeatManager(n: Int) {
private val minHeap = PriorityQueue<Int>()
init {
for (i in 1..n) minHeap.offer(i)
}
fun reserve(): Int = minHeap.poll()
fun unreserve(seatNumber: Int) {
minHeap.offer(seatNumber)
}
}⭐2: Min Heap + Lazy Initialization#
- 概念: 用計數器
nextSeat延遲分配座位，heap 只存被 unreserve 回收的座位，避免初始化大量元素 - 時間複雜度: reserve/unreserve
O(log n) - 空間複雜度:
O(m)- m 為 unreserve 的次數
class SeatManager(n: Int) {
private val minHeap = PriorityQueue<Int>()
private var nextSeat = 1
fun reserve(): Int {
return if (minHeap.isNotEmpty()) {
minHeap.poll()
} else {
nextSeat++
nextSeat - 1
}
}
fun unreserve(seatNumber: Int) {
minHeap.offer(seatNumber)
}
}🔑 Takeaways#
- Pattern: 「取最小可用」問題用 Min Heap
- 關鍵技巧: Lazy initialization 可以避免一次性初始化大量資料，用計數器追蹤下一個未使用的座位，heap 只存回收的座位