解題說明
Exam Room
題目描述： 有一排 n 個座位（編號 0 到 n-1）。當學生進入考場時，要選擇離最近的人最遠的座位坐下。如果有多個座位距離相同，選編號最小的。實作 seat() 和 leave(p) 兩個操作。
解題思路：
- 有序集合（Ordered Set）：維護已佔用座位的有序集合。
- seat() 操作：遍歷所有相鄰已佔座位之間的空隙，計算每個空隙中間位置到最近已佔座位的距離。特別處理頭（到座位 0）和尾（到座位 n-1）的邊界情況。選擇距離最大的空隙中間位置。
- leave(p) 操作：從有序集合中移除座位 p。
- 頭部空隙：第一個已佔座位到 0 的距離就是其座位編號。尾部空隙：n-1 減去最後一個已佔座位的編號。中間空隙：兩個相鄰已佔座位的距離的一半。
C++ 解法
複雜度分析
時間複雜度：seat() 為 O(k)，其中 k 為當前已佔座位數；leave() 為 O(log k)
空間複雜度：O(k) — 存儲已佔座位的有序集合
虛擬碼
1. Maintain a sorted set of occupied seats
2. seat():
a. If set is empty, sit at seat 0
b. Compute distance from seat 0 to first occupied seat (head gap)
c. For each pair of adjacent occupied seats (prev, cur):
- Compute mid-gap distance = (cur - prev) / 2
- Track maximum distance and corresponding seat
d. Compute distance from last occupied seat to n-1 (tail gap)
e. Insert and return the seat with maximum distance (smallest index on tie)
3. leave(p): remove p from the set其他解法
-
最大堆（Priority Queue）方法：將所有空隙 (start, end) 放入最大堆，按「距離, -起始位置」排序。seat() 從堆頂取出最大空隙，分裂成兩個子空隙放回堆。leave() 需要合併相鄰空隙（使用延遲刪除）。seat() 和 leave() 均為 O(log n)，但實作較複雜。
-
暴力模擬：用布林陣列標記每個座位狀態。seat() 時遍歷所有空座位計算最小距離。時間 O(n) per seat()，適合 n 很小的情況。
延伸思考
- 如果要支持「查詢當前最遠距離」但不實際坐下的操作，如何高效實現？
- 如果座位是二維排列（矩陣形），離最近的人最遠應如何定義和求解？
- 如何用平衡 BST 或跳表將 seat() 優化到 O(log k)？