解題說明
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 的線程安全？