解題說明
Seat Reservation Manager
題目描述: 設計一個座位預訂管理系統,管理從 1 到 n 編號的座位。支援兩個操作:
reserve():預訂並回傳編號最小的未預訂座位。unreserve(seatNumber):取消指定座位的預訂。
解題思路: 使用最小堆(min-heap)維護所有可用座位。
- 初始化:不需要將所有 n 個座位都放入堆中(可能 n 很大)。用一個計數器
next記錄下一個從未被預訂過的座位號。 reserve():若堆非空,取堆頂(最小編號);否則使用next++。unreserve(seat):將座位放回堆中。
這樣可以保證 reserve 總是回傳最小的可用編號。
C++ 解法
複雜度分析
時間複雜度:reserve O(log n)、unreserve O(log n) — 堆的插入和提取操作。初始化 O(1)。
空間複雜度:O(n) — 最壞情況下堆中存放 O(n) 個被取消預訂的座位。
虛擬碼
1. Initialize min-heap available = empty, next = 1 2. reserve(): a. If heap is not empty: pop and return the minimum b. Else: return next, then increment next 3. unreserve(seatNumber): a. Push seatNumber into the heap
其他解法
有序集合(TreeSet)O(log n):用 std::set<int> 替代堆,同樣支持取最小值和插入。功能等價但常數因子略大。
初始化全部座位 O(n):建構時將 1 到 n 全部放入堆。簡單直觀但初始化慢(O(n)),且 n 很大時浪費記憶體。延遲分配(lazy allocation)更優。
延伸思考
- 如果 reserve 需要回傳「最接近給定位置」的座位,如何修改資料結構?
- 如果需要支援批量預訂(一次預訂連續 k 個座位),如何設計?
- 在多執行緒環境下,如何保證 reserve 和 unreserve 的線程安全?