題目描述:給定兩個人的空閒時段清單 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]。時間複雜度: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)。只適合兩個清單均極短的場景。