解題說明
Meeting Scheduler
題目描述：給定兩個人的空閒時段清單 slots1 和 slots2（每個時段為 [start, end] 的半開區間），以及會議時長 duration。找出兩人共同空閒、且長度足夠 duration 的最早時段，以 [start, start+duration] 形式回傳。若不存在則回傳空陣列。
解題思路：雙指針法：
- 將
slots1和slots2分別按開始時間排序。 - 使用兩個指針
i和j分別指向兩個清單的當前時段。 - 計算當前兩個時段的交集：
lo = max(slots1[i][0], slots2[j][0])，hi = min(slots1[i][1], slots2[j][1])。 - 若
hi - lo >= duration，則找到答案，回傳[lo, lo + duration]。 - 否則，移動結束時間較早的那個指針（其時段已無法與當前另一方時段有更好交集）。
- 若兩個清單都遍歷完畢仍未找到，回傳空陣列。
C++ 解法
複雜度分析
時間複雜度：O(m log m + n log n) — 排序 slots1（m 個）和 slots2（n 個）各需 O(m log m) 和 O(n log n)；雙指針掃描為 O(m + n)。整體由排序主導。
空間複雜度：O(1) — 雙指針只使用常數額外空間（不計排序的棧空間）。
虛擬碼
1. Sort slots1 and slots2 by start time. 2. Initialize i = 0, j = 0. 3. While i < len(slots1) and j < len(slots2): a. lo = max(slots1[i][0], slots2[j][0]). b. hi = min(slots1[i][1], slots2[j][1]). c. If hi - lo >= duration: return [lo, lo + duration]. d. If slots1[i][1] < slots2[j][1]: i++. Else: j++. 4. Return [].
其他解法
方法一：最小堆合併 將兩個清單的所有時段加入最小堆（按開始時間），依次取出並檢查當前堆頂與前一個時段的交集。可推廣到 k 個人的排程，時間複雜度 O((m+n) log 2) = O(m+n)（堆固定大小 2），但對兩人情況不如雙指針直觀。
方法二：合併所有時段後求交集 先對兩人各自的時段取聯集（處理重疊），再對兩個聯集求交集，從交集中找長度 ≥ duration 的最早段。邏輯分步清晰，但需要額外空間儲存聯集結果，時間複雜度相同。
方法三：暴力配對
對 slots1 的每個時段與 slots2 的每個時段兩兩比較求交集，時間 O(mn)。只適合兩個清單均極短的場景。
延伸思考
- 若有 k 個人（k > 2）各有若干空閒時段，如何擴展算法找到 k 人共同可用的最早時段？
- 若時段不是靜態的，而是動態插入（新增或刪除空閒時段），如何設計資料結構支援高效的排程查詢？
- 若會議時長不固定（每次查詢帶不同的 duration），如何預處理使每次查詢更快？