題目描述: 設計一個座位預訂管理系統,管理從 1 到 n 編號的座位。支援兩個操作:
reserve():預訂並回傳編號最小的未預訂座位。unreserve(seatNumber):取消指定座位的預訂。解題思路: 使用最小堆(min-heap)維護所有可用座位。
next 記錄下一個從未被預訂過的座位號。reserve():若堆非空,取堆頂(最小編號);否則使用 next++。unreserve(seat):將座位放回堆中。這樣可以保證 reserve 總是回傳最小的可用編號。
時間複雜度: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)更優。