高效求解區(qū)間列表交集的算法指南：雙指針?lè)ㄉ疃冉馕?/h1>
1. Understanding Interval List Intersections
1.1 Problem Statement & Constraints
我們面對(duì)的場(chǎng)景需要找出兩個(gè)有序區(qū)間列表的交集。想象兩個(gè)日程安排表，每個(gè)表里都記錄著非重疊的時(shí)間段，且這些時(shí)間段按起始時(shí)間排序。任務(wù)就是找出這兩個(gè)日程表中所有重疊的時(shí)間段，這些重疊段代表兩人同時(shí)空閑的時(shí)間窗口。例如醫(yī)生A的接診時(shí)間和患者B的預(yù)約時(shí)段重疊的部分，就是實(shí)際可安排診療的時(shí)段。
題目要求輸出結(jié)果必須保持有序且無(wú)重疊，這與輸入列表的特性一致。關(guān)鍵約束包括：輸入列表的單個(gè)區(qū)間滿足start <= end，兩個(gè)原始列表各自內(nèi)部無(wú)重疊，但列表之間可能有任意數(shù)量的交集。時(shí)間復(fù)雜度需要控制在O(m+n)級(jí)別，避免嵌套循環(huán)暴力解。
1.2 Input/Output Format Examples
輸入樣例可能長(zhǎng)這樣：
firstList = [[0,2],[5,10],[13,23],[24,25]]
secondList = [[1,5],[8,12],[15,24],[25,26]]
對(duì)應(yīng)的輸出應(yīng)為：
[[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
觀察發(fā)現(xiàn)，每個(gè)交集區(qū)間的起始點(diǎn)是兩個(gè)原始區(qū)間起始點(diǎn)的較大值，結(jié)束點(diǎn)是兩個(gè)區(qū)間結(jié)束點(diǎn)的較小值。特別留意像[5,5]這種單點(diǎn)區(qū)間，說(shuō)明兩個(gè)區(qū)間在時(shí)間點(diǎn)5處剛好接觸。而[24,24]來(lái)自第一個(gè)列表的[24,25]和第二個(gè)列表的[15,24]的端點(diǎn)重疊。這種邊界條件的處理對(duì)解題非常關(guān)鍵。
2. Core Concept: Overlapping Interval Detection
2.1 Visualizing Interval Overlap Patterns
想象兩根不同顏色的熒光筆在時(shí)間軸上畫(huà)線段：黃色代表第一個(gè)醫(yī)生的接診時(shí)段，藍(lán)色代表第二個(gè)患者的空閑時(shí)間。當(dāng)這兩根熒光筆的色塊有部分覆蓋時(shí)，就形成了交集區(qū)間。比如黃色塊[5,10]和藍(lán)色塊[8,12]在8到10之間疊加出綠色區(qū)域——這就是我們要找的交集。
常見(jiàn)的重疊模式包括"完全包裹"（一個(gè)區(qū)間完全包含另一個(gè)）、"頭部插入"（一個(gè)區(qū)間的起點(diǎn)在另一個(gè)區(qū)間內(nèi)部）、"尾部拖拽"（一個(gè)區(qū)間的終點(diǎn)在另一個(gè)區(qū)間內(nèi)部），以及"端點(diǎn)輕觸"（一個(gè)區(qū)間的終點(diǎn)剛好是另一個(gè)的起點(diǎn)）。這些模式像是拼圖碎片間的接觸方式，拼圖能拼接的地方就是我們需要的交集。
2.2 Mathematical Conditions for Intersection
判斷兩個(gè)區(qū)間[A_start, A_end]和[B_start, B_end]是否存在交集，本質(zhì)是確認(rèn)它們的時(shí)間線有共存的時(shí)刻。這個(gè)條件可以用一個(gè)簡(jiǎn)潔的邏輯表達(dá)式表達(dá)：當(dāng)且僅當(dāng)A_start <= B_end且B_start <= A_end時(shí)，兩區(qū)間必相交。
比如當(dāng)A區(qū)間結(jié)束于5（A_end=5）而B(niǎo)區(qū)間開(kāi)始于3（B_start=3），只要B的起點(diǎn)不超過(guò)A的終點(diǎn)（3<=5成立），同時(shí)A的起點(diǎn)也小于等于B的終點(diǎn)，交集就存在。這個(gè)雙向檢查如同確認(rèn)兩個(gè)人在握手時(shí)是否同時(shí)伸出右手——只有雙方的手在空間上同時(shí)存在交集區(qū)域，握手才能發(fā)生。實(shí)際計(jì)算時(shí)，交集的起點(diǎn)取兩者的較大值，終點(diǎn)取較小值，這樣就能準(zhǔn)確框定重疊區(qū)域。
3. Algorithm Walkthrough
3.1 Two-Pointer Approach Explained
想象你同時(shí)拿著兩根激光筆，一束紅光掃描第一個(gè)醫(yī)生的排班表，一束藍(lán)光掃描第二個(gè)患者的空閑表。雙指針?lè)ǖ暮诵木褪亲屵@兩束光在各自的區(qū)間列表上同步推進(jìn)，每次只關(guān)注當(dāng)前兩個(gè)區(qū)間的交互。當(dāng)紅光標(biāo)在醫(yī)生A的[1,3]時(shí)段，藍(lán)光標(biāo)在患者B的[2,5]時(shí)段時(shí)，我們立即檢查這兩個(gè)時(shí)間段是否有交集。
這種方法的精妙之處在于指針的移動(dòng)策略?？偸窍忍幚懋?dāng)前兩個(gè)區(qū)間中結(jié)束時(shí)間較早的那個(gè)，就像兩個(gè)人賽跑時(shí)，先給跑得慢的人遞水。比如醫(yī)生A的當(dāng)前時(shí)段結(jié)束在3點(diǎn)，患者B的當(dāng)前時(shí)段結(jié)束在5點(diǎn)，處理完他們的交集后，我們只需要移動(dòng)醫(yī)生A的指針，因?yàn)樗臅r(shí)段更早結(jié)束，不會(huì)與患者B的下個(gè)時(shí)段產(chǎn)生交集了。
3.2 Step-by-Step Intersection Logic
實(shí)際操作時(shí)，我們的手指會(huì)在草稿紙上這樣滑動(dòng)：當(dāng)兩個(gè)指針i和j分別指向firstList[i]和secondList[j]，先取出它們的start和end值。如果發(fā)現(xiàn)firstList[i]的end小于secondList[j]的start，說(shuō)明醫(yī)生的排班太早，患者還沒(méi)空閑，此時(shí)直接i++；反之同理j++。
當(dāng)兩個(gè)區(qū)間確實(shí)存在交集時(shí)（通過(guò)第二章的數(shù)學(xué)條件確認(rèn)），就像兩個(gè)發(fā)光的樂(lè)高積木拼合在一起。此時(shí)交集區(qū)間的start是兩個(gè)區(qū)間start的較大值，end是兩個(gè)end的較小值。記錄完這個(gè)交集后，要像吃餅干時(shí)先吃掉更小塊的那片一樣，移動(dòng)結(jié)束時(shí)間較早的那個(gè)區(qū)間的指針。
3.3 Edge Case Handling
當(dāng)遇到醫(yī)生A的[5,7]完全包裹患者B的[6,6]時(shí)，算法會(huì)自動(dòng)計(jì)算start=max(5,6)=6，end=min(7,6)=6，生成合法區(qū)間[6,6]。這解決了單點(diǎn)區(qū)間的特殊情況。對(duì)于剛好頭尾相接的區(qū)間比如[2,5]和[5,8]，算法通過(guò)數(shù)學(xué)條件5<=5成立判斷出存在交集，生成[5,5]這個(gè)有效區(qū)間。
當(dāng)某個(gè)列表提前掃描完畢時(shí)，比如醫(yī)生的排班表已經(jīng)檢查到最后一個(gè)時(shí)段，而患者還有三個(gè)空閑時(shí)段未處理，算法會(huì)自動(dòng)終止。這種設(shè)計(jì)保證不會(huì)出現(xiàn)數(shù)組越界，就像音樂(lè)會(huì)散場(chǎng)時(shí)保安會(huì)逐個(gè)檢查每個(gè)出口，確認(rèn)沒(méi)有樂(lè)迷滯留后才停止工作。
4. Optimization & Implementation
4.1 Time Complexity Analysis (O(m+n) Proof)
雙指針?lè)ǖ臅r(shí)間復(fù)雜度像兩輛并行的地鐵列車，每輛只沿固定軌道單向行駛。假設(shè)第一個(gè)醫(yī)生排班表有m個(gè)時(shí)段，第二個(gè)患者空閑表有n個(gè)時(shí)段。每個(gè)指針i和j最多各自移動(dòng)m次和n次，在while循環(huán)中每次至少有一個(gè)指針向前移動(dòng)。整個(gè)過(guò)程就像用剪刀裁剪兩條并排的彩帶，剪刀尖總共劃過(guò)的距離不會(huì)超過(guò)m+n。
這種線性復(fù)雜度比暴力解法O(m*n)高效得多，尤其在處理醫(yī)療系統(tǒng)的萬(wàn)級(jí)排班數(shù)據(jù)時(shí)優(yōu)勢(shì)明顯。我們可以想象指針移動(dòng)軌跡如同兩列士兵在閱兵式上的行進(jìn)，紅藍(lán)方陣各自走完自己的隊(duì)列長(zhǎng)度后，整個(gè)檢閱儀式自然結(jié)束，不存在回頭或重復(fù)檢查的情況。
4.2 Code Structure Breakdown
代碼結(jié)構(gòu)像精心設(shè)計(jì)的俄羅斯套娃，外層是結(jié)果列表的初始化，中間層是雙指針控制的循環(huán)，最內(nèi)層是交集計(jì)算。我們首先定義i,j兩個(gè)指針和result空列表。循環(huán)條件設(shè)置為while i < len(A) and j < len(B)，這就像給兩個(gè)指針系上安全繩，防止數(shù)組越界。
核心操作部分像拼圖游戲的三步走：1）計(jì)算當(dāng)前兩個(gè)區(qū)間的最大start和最小end；2）當(dāng)最大start ≤ 最小end時(shí)確認(rèn)存在交集；3）根據(jù)誰(shuí)的end更小來(lái)決定移動(dòng)哪個(gè)指針。這種設(shè)計(jì)讓代碼像精密的鐘表齒輪，每個(gè)動(dòng)作都觸發(fā)下一個(gè)邏輯步驟，例如當(dāng)A[i][1] < B[j][1]時(shí)i+=1，就像天平傾斜后向較輕側(cè)添加砝碼。
4.3 Testing Your Solution
測(cè)試用例應(yīng)該像彩虹的七種顏色覆蓋所有可能場(chǎng)景。構(gòu)造一個(gè)[[1,2],[5,5]]與[[4,10]]的測(cè)試案例，驗(yàn)證算法能否正確處理單點(diǎn)區(qū)間與長(zhǎng)區(qū)間的交集。當(dāng)遇到[[13,15]]和[[1,1],[2,2]]時(shí)，應(yīng)當(dāng)返回空列表，這能檢驗(yàn)算法處理完全不重疊情況的能力。
實(shí)際調(diào)試時(shí)可以想象自己是交通管制員，給每個(gè)區(qū)間對(duì)打信號(hào)燈：綠燈（有交集加入結(jié)果）、黃燈（移動(dòng)較慢的指針）、紅燈（停止循環(huán)）。特別要注意當(dāng)某個(gè)列表為空時(shí)，代碼應(yīng)立即返回空列表而不是進(jìn)入循環(huán)，這就像電梯感應(yīng)到無(wú)人候梯時(shí)會(huì)直接跳過(guò)?？繕菍?。
掃描二維碼推送至手機(jī)訪問(wèn)。
版權(quán)聲明：本文由皇冠云發(fā)布，如需轉(zhuǎn)載請(qǐng)注明出處。
1. Understanding Interval List Intersections
1.1 Problem Statement & Constraints
我們面對(duì)的場(chǎng)景需要找出兩個(gè)有序區(qū)間列表的交集。想象兩個(gè)日程安排表，每個(gè)表里都記錄著非重疊的時(shí)間段，且這些時(shí)間段按起始時(shí)間排序。任務(wù)就是找出這兩個(gè)日程表中所有重疊的時(shí)間段，這些重疊段代表兩人同時(shí)空閑的時(shí)間窗口。例如醫(yī)生A的接診時(shí)間和患者B的預(yù)約時(shí)段重疊的部分，就是實(shí)際可安排診療的時(shí)段。
題目要求輸出結(jié)果必須保持有序且無(wú)重疊，這與輸入列表的特性一致。關(guān)鍵約束包括：輸入列表的單個(gè)區(qū)間滿足start <= end，兩個(gè)原始列表各自內(nèi)部無(wú)重疊，但列表之間可能有任意數(shù)量的交集。時(shí)間復(fù)雜度需要控制在O(m+n)級(jí)別，避免嵌套循環(huán)暴力解。
1.2 Input/Output Format Examples
輸入樣例可能長(zhǎng)這樣：
firstList = [[0,2],[5,10],[13,23],[24,25]]
secondList = [[1,5],[8,12],[15,24],[25,26]]
對(duì)應(yīng)的輸出應(yīng)為：
[[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
觀察發(fā)現(xiàn)，每個(gè)交集區(qū)間的起始點(diǎn)是兩個(gè)原始區(qū)間起始點(diǎn)的較大值，結(jié)束點(diǎn)是兩個(gè)區(qū)間結(jié)束點(diǎn)的較小值。特別留意像[5,5]這種單點(diǎn)區(qū)間，說(shuō)明兩個(gè)區(qū)間在時(shí)間點(diǎn)5處剛好接觸。而[24,24]來(lái)自第一個(gè)列表的[24,25]和第二個(gè)列表的[15,24]的端點(diǎn)重疊。這種邊界條件的處理對(duì)解題非常關(guān)鍵。
2. Core Concept: Overlapping Interval Detection
2.1 Visualizing Interval Overlap Patterns
想象兩根不同顏色的熒光筆在時(shí)間軸上畫(huà)線段：黃色代表第一個(gè)醫(yī)生的接診時(shí)段，藍(lán)色代表第二個(gè)患者的空閑時(shí)間。當(dāng)這兩根熒光筆的色塊有部分覆蓋時(shí)，就形成了交集區(qū)間。比如黃色塊[5,10]和藍(lán)色塊[8,12]在8到10之間疊加出綠色區(qū)域——這就是我們要找的交集。
常見(jiàn)的重疊模式包括"完全包裹"（一個(gè)區(qū)間完全包含另一個(gè)）、"頭部插入"（一個(gè)區(qū)間的起點(diǎn)在另一個(gè)區(qū)間內(nèi)部）、"尾部拖拽"（一個(gè)區(qū)間的終點(diǎn)在另一個(gè)區(qū)間內(nèi)部），以及"端點(diǎn)輕觸"（一個(gè)區(qū)間的終點(diǎn)剛好是另一個(gè)的起點(diǎn)）。這些模式像是拼圖碎片間的接觸方式，拼圖能拼接的地方就是我們需要的交集。
2.2 Mathematical Conditions for Intersection
判斷兩個(gè)區(qū)間[A_start, A_end]和[B_start, B_end]是否存在交集，本質(zhì)是確認(rèn)它們的時(shí)間線有共存的時(shí)刻。這個(gè)條件可以用一個(gè)簡(jiǎn)潔的邏輯表達(dá)式表達(dá)：當(dāng)且僅當(dāng)A_start <= B_end且B_start <= A_end時(shí)，兩區(qū)間必相交。
比如當(dāng)A區(qū)間結(jié)束于5（A_end=5）而B(niǎo)區(qū)間開(kāi)始于3（B_start=3），只要B的起點(diǎn)不超過(guò)A的終點(diǎn)（3<=5成立），同時(shí)A的起點(diǎn)也小于等于B的終點(diǎn)，交集就存在。這個(gè)雙向檢查如同確認(rèn)兩個(gè)人在握手時(shí)是否同時(shí)伸出右手——只有雙方的手在空間上同時(shí)存在交集區(qū)域，握手才能發(fā)生。實(shí)際計(jì)算時(shí)，交集的起點(diǎn)取兩者的較大值，終點(diǎn)取較小值，這樣就能準(zhǔn)確框定重疊區(qū)域。
3. Algorithm Walkthrough
3.1 Two-Pointer Approach Explained
想象你同時(shí)拿著兩根激光筆，一束紅光掃描第一個(gè)醫(yī)生的排班表，一束藍(lán)光掃描第二個(gè)患者的空閑表。雙指針?lè)ǖ暮诵木褪亲屵@兩束光在各自的區(qū)間列表上同步推進(jìn)，每次只關(guān)注當(dāng)前兩個(gè)區(qū)間的交互。當(dāng)紅光標(biāo)在醫(yī)生A的[1,3]時(shí)段，藍(lán)光標(biāo)在患者B的[2,5]時(shí)段時(shí)，我們立即檢查這兩個(gè)時(shí)間段是否有交集。
這種方法的精妙之處在于指針的移動(dòng)策略?？偸窍忍幚懋?dāng)前兩個(gè)區(qū)間中結(jié)束時(shí)間較早的那個(gè)，就像兩個(gè)人賽跑時(shí)，先給跑得慢的人遞水。比如醫(yī)生A的當(dāng)前時(shí)段結(jié)束在3點(diǎn)，患者B的當(dāng)前時(shí)段結(jié)束在5點(diǎn)，處理完他們的交集后，我們只需要移動(dòng)醫(yī)生A的指針，因?yàn)樗臅r(shí)段更早結(jié)束，不會(huì)與患者B的下個(gè)時(shí)段產(chǎn)生交集了。
3.2 Step-by-Step Intersection Logic
實(shí)際操作時(shí)，我們的手指會(huì)在草稿紙上這樣滑動(dòng)：當(dāng)兩個(gè)指針i和j分別指向firstList[i]和secondList[j]，先取出它們的start和end值。如果發(fā)現(xiàn)firstList[i]的end小于secondList[j]的start，說(shuō)明醫(yī)生的排班太早，患者還沒(méi)空閑，此時(shí)直接i++；反之同理j++。
當(dāng)兩個(gè)區(qū)間確實(shí)存在交集時(shí)（通過(guò)第二章的數(shù)學(xué)條件確認(rèn)），就像兩個(gè)發(fā)光的樂(lè)高積木拼合在一起。此時(shí)交集區(qū)間的start是兩個(gè)區(qū)間start的較大值，end是兩個(gè)end的較小值。記錄完這個(gè)交集后，要像吃餅干時(shí)先吃掉更小塊的那片一樣，移動(dòng)結(jié)束時(shí)間較早的那個(gè)區(qū)間的指針。
3.3 Edge Case Handling
當(dāng)遇到醫(yī)生A的[5,7]完全包裹患者B的[6,6]時(shí)，算法會(huì)自動(dòng)計(jì)算start=max(5,6)=6，end=min(7,6)=6，生成合法區(qū)間[6,6]。這解決了單點(diǎn)區(qū)間的特殊情況。對(duì)于剛好頭尾相接的區(qū)間比如[2,5]和[5,8]，算法通過(guò)數(shù)學(xué)條件5<=5成立判斷出存在交集，生成[5,5]這個(gè)有效區(qū)間。
當(dāng)某個(gè)列表提前掃描完畢時(shí)，比如醫(yī)生的排班表已經(jīng)檢查到最后一個(gè)時(shí)段，而患者還有三個(gè)空閑時(shí)段未處理，算法會(huì)自動(dòng)終止。這種設(shè)計(jì)保證不會(huì)出現(xiàn)數(shù)組越界，就像音樂(lè)會(huì)散場(chǎng)時(shí)保安會(huì)逐個(gè)檢查每個(gè)出口，確認(rèn)沒(méi)有樂(lè)迷滯留后才停止工作。
4. Optimization & Implementation
4.1 Time Complexity Analysis (O(m+n) Proof)
雙指針?lè)ǖ臅r(shí)間復(fù)雜度像兩輛并行的地鐵列車，每輛只沿固定軌道單向行駛。假設(shè)第一個(gè)醫(yī)生排班表有m個(gè)時(shí)段，第二個(gè)患者空閑表有n個(gè)時(shí)段。每個(gè)指針i和j最多各自移動(dòng)m次和n次，在while循環(huán)中每次至少有一個(gè)指針向前移動(dòng)。整個(gè)過(guò)程就像用剪刀裁剪兩條并排的彩帶，剪刀尖總共劃過(guò)的距離不會(huì)超過(guò)m+n。
這種線性復(fù)雜度比暴力解法O(m*n)高效得多，尤其在處理醫(yī)療系統(tǒng)的萬(wàn)級(jí)排班數(shù)據(jù)時(shí)優(yōu)勢(shì)明顯。我們可以想象指針移動(dòng)軌跡如同兩列士兵在閱兵式上的行進(jìn)，紅藍(lán)方陣各自走完自己的隊(duì)列長(zhǎng)度后，整個(gè)檢閱儀式自然結(jié)束，不存在回頭或重復(fù)檢查的情況。
4.2 Code Structure Breakdown
代碼結(jié)構(gòu)像精心設(shè)計(jì)的俄羅斯套娃，外層是結(jié)果列表的初始化，中間層是雙指針控制的循環(huán)，最內(nèi)層是交集計(jì)算。我們首先定義i,j兩個(gè)指針和result空列表。循環(huán)條件設(shè)置為while i < len(A) and j < len(B)，這就像給兩個(gè)指針系上安全繩，防止數(shù)組越界。
核心操作部分像拼圖游戲的三步走：1）計(jì)算當(dāng)前兩個(gè)區(qū)間的最大start和最小end；2）當(dāng)最大start ≤ 最小end時(shí)確認(rèn)存在交集；3）根據(jù)誰(shuí)的end更小來(lái)決定移動(dòng)哪個(gè)指針。這種設(shè)計(jì)讓代碼像精密的鐘表齒輪，每個(gè)動(dòng)作都觸發(fā)下一個(gè)邏輯步驟，例如當(dāng)A[i][1] < B[j][1]時(shí)i+=1，就像天平傾斜后向較輕側(cè)添加砝碼。
4.3 Testing Your Solution
測(cè)試用例應(yīng)該像彩虹的七種顏色覆蓋所有可能場(chǎng)景。構(gòu)造一個(gè)[[1,2],[5,5]]與[[4,10]]的測(cè)試案例，驗(yàn)證算法能否正確處理單點(diǎn)區(qū)間與長(zhǎng)區(qū)間的交集。當(dāng)遇到[[13,15]]和[[1,1],[2,2]]時(shí)，應(yīng)當(dāng)返回空列表，這能檢驗(yàn)算法處理完全不重疊情況的能力。
實(shí)際調(diào)試時(shí)可以想象自己是交通管制員，給每個(gè)區(qū)間對(duì)打信號(hào)燈：綠燈（有交集加入結(jié)果）、黃燈（移動(dòng)較慢的指針）、紅燈（停止循環(huán)）。特別要注意當(dāng)某個(gè)列表為空時(shí)，代碼應(yīng)立即返回空列表而不是進(jìn)入循環(huán)，這就像電梯感應(yīng)到無(wú)人候梯時(shí)會(huì)直接跳過(guò)?？繕菍?。
掃描二維碼推送至手機(jī)訪問(wèn)。
版權(quán)聲明：本文由皇冠云發(fā)布，如需轉(zhuǎn)載請(qǐng)注明出處。