如果你在力扣上刷題刷到數(shù)組/區(qū)間這個專題大概率會和合并區(qū)間這道題打個照面。LeetCode 56. Merge Intervals 是面試里的老熟人在ACwing的算法基礎(chǔ)課里它又叫“區(qū)間合并”模板題幾乎是排序?qū)ｎ}開篇就練的骨架級題目。我第一次把它當模板背下來的時候覺得排序加掃描這個思路理所當然等自己真上手寫才發(fā)現(xiàn)里面門道不少比較器怎么寫、最后一個區(qū)間為什么總丟、碰到 [1,5] 和 [2,3] 這種包含關(guān)系時為什么必須取 max 而不是直接覆蓋。這篇文章我就把這題從題目拆解到三種語言實現(xiàn)再到幾個容易踩的坑和它的變形題一次講清楚。適合準備校招面試、刷競賽模板或者想把區(qū)間類題目徹底搞利索的同學。1. 題目拆解合并區(qū)間到底在考什么1.1 一眼識別題目特征題目輸入是一組區(qū)間形如 intervals[i] [start_i, end_i]要求把所有有重疊的區(qū)間合并輸出一個新的區(qū)間數(shù)組。力扣原題給的那個例子最有代表性intervals [[1,3],[2,6],[8,10],[15,18]]輸出 [[1,6],[8,10],[15,18]]。因為 [1,3] 和 [2,6] 在 2 和 3 之間重疊合并成 [1,6]其他兩個區(qū)間和它倆隔開了保持原樣?？吹竭@種描述第一反應(yīng)就應(yīng)該是排序題、貪心題、區(qū)間掃描題。還有一個特征容易被忽視輸入順序完全是亂的沒有任何規(guī)律。換句話說出題人不會好心幫你把區(qū)間按起點排好。如果你拿到題目后第一反應(yīng)是“那我遍歷數(shù)組拿每個區(qū)間和后面的區(qū)間兩兩比較”這就是典型的直覺錯誤后面我會解釋為什么這種暴力做法在遇到鏈式合并時會非常麻煩。另一個重要特征是區(qū)間端點值范圍力扣 56 里 start_i 和 end_i 都在 -10^4 到 10^4 之間區(qū)間數(shù)量最多 10^4 個。這個數(shù)據(jù)規(guī)模意味著 O(n log n) 的排序解法是標準答案也意味著你完全可以先花 O(n log n) 做排序再做 O(n) 掃描整體依然是一個能穩(wěn)過的解法。1.2 為什么排序是這道題的命門我先模擬一下不排序的暴力法會撞到什么。假設(shè)你已經(jīng)往結(jié)果列表里放了一個 [1,5]現(xiàn)在來了個 [2,3]它被 [1,5] 包含合并結(jié)果還是 [1,5]接著又來了個 [4,6]它跟 [1,5] 相交于是結(jié)果變成 [1,6]此時如果之前還有個 [3,4] 沒處理它其實早就被包進去了。問題在于區(qū)間之間的重疊關(guān)系是“鏈式傳播”的你不排序就無法預(yù)知哪個區(qū)間會觸發(fā)下一輪合并處理順序稍有不同結(jié)果列表就在不斷被改寫。在這種狀態(tài)下要做到一遍掃描完美合并基本要靠維護有序結(jié)構(gòu)代價不比排序低。把區(qū)間按起點升序排好之后整個問題一下子變單純了。因為左端點單調(diào)不減任何一個新區(qū)間都只會出現(xiàn)在當前合并區(qū)間的“右方或內(nèi)部”不會再跑回前面去糾纏已合并完的區(qū)間。此時你只需要干一件事維護一個“當前正在合并的區(qū)間”用 curStart 記左端點curEnd 記右端點。每次遇到新區(qū)間如果它的左端點還在 curEnd 的覆蓋范圍內(nèi)說明和當前區(qū)間重疊或相接那就把 curEnd 更新成兩者的最大值如果它的左端點已經(jīng)越過了 curEnd說明從 curStart 開始的那段合并徹底結(jié)束了把它存進結(jié)果列表再拿當前區(qū)間作為新的合并起點。整個過程從左到右掃一遍不回溯中間結(jié)果也不會被后續(xù)區(qū)間推翻。用生活里的例子理解更直觀。想象你有一堆日程安排把每段日程按開始時間排好隊。然后從頭往后看如果下一條日程的開始時間早于等于當前這段合并日程的結(jié)束時間就把這段合并日程的結(jié)束時間往后推到更晚的那個如果下一條日程的開始時間已經(jīng)比當前合并日程的結(jié)束時間還晚說明中間有空檔這個合并日程可以定稿了。你從頭掃到尾所有日程就自然被分成了連續(xù)的大塊。1.3 貪心合并的循環(huán)不變量不少同學覺得看懂樣例就夠了但面試時被追問“為什么這個貪心是對的”就容易卡殼。這里我可以提供一個很順的口徑也是算法圈子常說的循環(huán)不變量掃描到第 i 個區(qū)間時如果當前合并區(qū)間存在那么它表示“從 curStart 開始所有能連到 curEnd 的區(qū)間的最大右端點”結(jié)果列表里已經(jīng)保存的所有合并區(qū)間任意兩個都不重疊且已經(jīng)是最終答案的前綴。這個性質(zhì)在每次迭代后都保持要么把新區(qū)間并進當前區(qū)間curEnd 變?yōu)楦潞蟮淖畲笾敌再|(zhì)依然成立要么把當前區(qū)間定稿并開啟新的當前區(qū)間性質(zhì)依然成立。循環(huán)結(jié)束后再把最后一個當前區(qū)間定稿所有區(qū)間就被完整、無重疊地合并完畢。這也解釋了為什么合并時要寫 curEnd max(curEnd, intervals[i][1])而不是直接 curEnd intervals[i][1]。因為新區(qū)間可能完全被當前區(qū)間包含比如當前區(qū)間是 [1,5]新來的是 [2,3]如果直接覆蓋右端點從 5 變成 3等于把人家的合并范圍往回縮了后面的區(qū)間再拿 3 去比較結(jié)果必錯。max 這一步看似不起眼實際上是整個貪心正確性的地基。2. 排序選型為什么ACwing里一行sort就夠了2.1 ACwing模板里的區(qū)間合并骨架標題里特意寫了“ACwing模板題排序”說明這道題在競賽語境里是拿來當模板背的。ACwing 803 區(qū)間合并的經(jīng)典做法是這樣寫的#include bits/stdc.h using namespace std; typedef pairint, int PII; void merge(vectorPII segs) { sort(segs.begin(), segs.end()); // pair 默認先 first 后 second 升序 vectorPII res; int st -2e9, ed -2e9; // 哨兵區(qū)間 for (auto seg : segs) { if (ed seg.first) { // 注意是 而不是 if (st ! -2e9) res.push_back({st, ed}); st seg.first, ed seg.second; } else { ed max(ed, seg.second); } } if (st ! -2e9) res.push_back({st, ed}); }這段模板有兩個值得留意的設(shè)計。第一個是 pair 排序C 的 sort 對 pair 默認按字典序先比較 first再比較 second所以區(qū)間天然按起點升序、起點相同時按終點升序排列連自定義比較器都不用寫。第二個是哨兵值 -2e9因為區(qū)間值域不會低到 -2e9把初始區(qū)間的 st、ed 設(shè)成一個絕對不存在的區(qū)間就能讓第一個區(qū)間的處理也走同一個 if-else 分支最后再用 st ! -2e9 判斷到底有沒有處理過任何區(qū)間。這種哨兵寫法在競賽里很常見好處是邏輯統(tǒng)一壞處是代碼里多了一個魔法值閱讀時需要習慣。到了力扣 56輸入從 vectorpairint,int 變成了二維數(shù)組模板骨架完全不變變的只是排序?qū)懛ê瓦吔绯跏蓟绞?。所以你可以把這道題理解成同一套核心套路在兩個平臺上的兩種皮相。能背下這套骨架力扣 56、ACwing 803 其實就都拿下了。2.2 起點排序和終點排序怎么選合并區(qū)間用起點排序這是定了的。原因很簡單你要從左端點最小的區(qū)間開始“滾雪球”起點的順序決定了掃描過程是單向推進的。如果改成按終點排序你拿到第一個區(qū)間時根本不知道全局最左邊的區(qū)間是誰合并范圍隨時可能向左擴張只能反復(fù)調(diào)整結(jié)果復(fù)雜度就退化回 O(n^2) 甚至更糟。但并不是所有區(qū)間題都按起點排序這里我把常見的幾道題放在一張表里方便對照典型題目排序方式貪心維護的關(guān)鍵變量力扣 56 合并區(qū)間按起點升序當前合并區(qū)間的右端點最大值力扣 435 無重疊區(qū)間按終點升序上一個被保留區(qū)間的右端點力扣 452 用最少數(shù)量的箭引爆氣球按起點升序公共交集區(qū)間的右端點最小值力扣 1288 刪除被覆蓋區(qū)間起點升序、終點降序當前已覆蓋的最遠右端點看出來了嗎排序方向取決于你想要什么順序的“局部最優(yōu)”合并區(qū)間需要從前往后構(gòu)建連續(xù)塊所以起點升序無重疊區(qū)間希望盡早結(jié)束當前區(qū)間以容納更多答案所以終點升序氣球問題希望公共交集盡量向右擴展所以起點升序但維護的是右端點最小值。這道題的排序選擇不是拍腦袋而是貪心方向決定的。理解這一點后面試官把題目稍微變形你也能很快定出排序策略。2.3 寫排序比較器的三條鐵律力扣 56 在 Java 里要自己寫比較器這里我踩過幾次坑直接提煉成三條經(jīng)驗。第一條別用差值寫法 (a, b) - a[0] - b[0]。這種寫法在力扣 56 里可能不會出大問題因為端點值只有 -10^4 到 10^4但如果你把它帶到別的題比如坐標是 2^31 級別的區(qū)間a[0] - b[0] 可能溢出導(dǎo)致排序結(jié)果完全錯亂更致命的是這會破壞比較器的傳遞性。Java 的 TimSort 一旦檢測到“a 應(yīng)該排在 b 前b 應(yīng)該排在 c 前但 a 又比 c 小或等于”這種矛盾會直接拋異常。穩(wěn)妥寫法是 Integer.compare(a[0], b[0])。第二條如果考點允許優(yōu)先用語言自帶的能力。C 里 sort 對 pair 默認排序就是想要的Python 里 intervals.sort(keylambda x: x[0]) 一行搞定Java 里 Arrays.sort(intervals, (a, b) - Integer.compare(a[0], b[0]))。這里有個隱形的知識C 的 sort 對 vectorvector 也是按字典序排序的所以力扣 56 的 C 解法甚至可以不寫比較器默認 sort(intervals.begin(), intervals.end()) 就能用。第三條比較器只比較必要的維度。合并區(qū)間時第二維要不要排不需要。因為掃描合并用的是 max終點順序?qū)Y(jié)果沒有任何影響寫多了反而讓比較器復(fù)雜增加出錯概率。但如果你在寫 1288 刪除被覆蓋區(qū)間那種題就一定要起點升序、終點降序不能反過來我后面會講到。3. 三種語言完整實現(xiàn)與逐行剖析3.1 Java實現(xiàn)面試首選力扣上最主流的寫法是class Solution { public int[][] merge(int[][] intervals) { if (intervals null || intervals.length 1) { return intervals; } Arrays.sort(intervals, (a, b) - Integer.compare(a[0], b[0])); Listint[] merged new ArrayList(); int curStart intervals[0][0]; int curEnd intervals[0][1]; for (int i 1; i intervals.length; i) { if (intervals[i][0] curEnd) { curEnd Math.max(curEnd, intervals[i][1]); } else { merged.add(new int[]{curStart, curEnd}); curStart intervals[i][0]; curEnd intervals[i][1]; } } merged.add(new int[]{curStart, curEnd}); return merged.toArray(new int[merged.size()][]); } }這段代碼有四個落點要注意。第一是判空和長度小于等于 1 的快速返回除了避免空指針還能少想一個邊界分支。第二是排序后一定用 Integer.compare不用減法。第三是循環(huán)從 i1 開始因為第 0 個區(qū)間已經(jīng)承擔了 curStart 和 curEnd 的初始化工作。第四是循環(huán)結(jié)束后必須再執(zhí)行一次 merged.add把最后一組當前區(qū)間推進結(jié)果這一行忘掉就會出現(xiàn)經(jīng)典的“少一個區(qū)間”錯誤我在第四部分還會專門講。最后返回用的是 toArray(new int[merged.size()][])這個寫法是二維 List 轉(zhuǎn)數(shù)組的標準姿勢size 傳進去可以讓 Java 分配正確大小的數(shù)組避免擴容時的反射開銷。面試場景下Java 是這么寫的就基本滿意了。如果你還想再穩(wěn)一點可以把 intervals.length 1 的判斷拿掉讓循環(huán)從 i0 開始把邏輯改成先判斷 merged 是否為空但那種寫法在簡潔度上不如現(xiàn)在這版。3.2 Python實現(xiàn)刷題最快def merge(intervals): intervals.sort(keylambda x: x[0]) merged [] for interval in intervals: if not merged or merged[-1][1] interval[0]: merged.append(interval) else: merged[-1][1] max(merged[-1][1], interval[1]) return mergedPython 版是我私下刷題最常用的一版因為它可以直接原地修改 merged 列表里最后一個區(qū)間的右端點。關(guān)鍵判斷同樣要搞清楚merged[-1][1] interval[0] 表示“當前區(qū)間和結(jié)果列表最后一個區(qū)間沒有重疊”注意這里用的是小于而不是小于等于因為力扣 56 認為端點相接也算重疊需要合并如果你把小于改成小于等于[1,2] 和 [2,3] 就會錯誤地變成兩個區(qū)間。很多人寫 Python 版容易犯一個錯誤更新時寫成 merged[-1][1] interval[1]忘了取 max。比如 merged[-1] 是 [1,5]interval 是 [2,3]更新后右端點變成 3后面再拿 3 去和 [4,6] 比較會以為中間有空檔結(jié)果錯得離譜。所以哪怕在 Python 這種“看起來為所欲為”的語言里也要老老實實寫 max。3.3 C實現(xiàn)ACwing風格class Solution { public: vectorvectorint merge(vectorvectorint intervals) { if (intervals.empty()) return {}; sort(intervals.begin(), intervals.end()); // 默認字典序排序 vectorvectorint res; int st intervals[0][0], ed intervals[0][1]; for (int i 1; i intervals.size(); i) { if (intervals[i][0] ed) { ed max(ed, intervals[i][1]); } else { res.push_back({st, ed}); st intervals[i][0]; ed intervals[i][1]; } } res.push_back({st, ed}); return res; } };在這個版本里sort(intervals.begin(), intervals.end()) 對 vectorvector 的作用是按外層數(shù)組的字典序排序也就是先比第一個數(shù)再比第二個數(shù)。這個特性和 pair 排序其實是一回事所以 C 解法一行比較器都不用寫比 Java 干凈不少。如果你是從 ACwing 模板轉(zhuǎn)過來看這道題的會發(fā)現(xiàn)這段代碼和模板的區(qū)別主要在于模板用 Pair 和哨兵值這里用二維 vector 和第一個區(qū)間初始化。核心的 if (intervals[i][0] ed) 和 ed max(ed, intervals[i][1]) 完全一致。還有第三種更貼近 ACwing 原模板的寫法不判空直接初始化 st -2e9, ed -2e9循環(huán)所有區(qū)間最后再用哨兵判斷。這種寫法能寫出統(tǒng)一的循環(huán)結(jié)構(gòu)面試時可以提一嘴“我還有個競賽模板的寫法”但如果你現(xiàn)場手寫我還是建議用第一個區(qū)間初始化的版本分支更少不容易寫錯。3.4 邊界條件與復(fù)雜度核算把三種語言的實現(xiàn)放在一起看邊界條件的處理其實是同一套空輸入直接返回空單個區(qū)間直接返回所有區(qū)間重疊時只輸出一個區(qū)間不在同一塊時按順序輸出多個區(qū)間。還有一個容易被忽略的邊界是端點相接比如 [1,2] 和 [2,3]力扣 56 是能合并成 [1,3] 的所以判斷條件必須用 ed而不是 ed。如果你在別的題里見到“嚴格重疊”的說法那時才改成 。復(fù)雜度這塊很明確排序 O(n log n)一趟掃描 O(n)總時間復(fù)雜度 O(n log n)。空間上如果不把輸出數(shù)組算進去每個實現(xiàn)只需要常數(shù)個保存 curStart、curEnd 的變量算是 O(1) 輔助空間但要注意 Java 的 Arrays.sort 對對象數(shù)組使用 TimSort實際會申請 O(n) 的臨時數(shù)組嚴格算法分析里這可能算 O(n) 空間。競賽和力扣通常只看你遞推時的額外變量所以說不算輸出的 O(1) 輔助空間也能接受。面試被問到時最好主動說清楚“我看作 O(log n) 是排序遞歸棧嚴格一點是 O(n)”表示你想過這層比光背一個 O(1) 要加分。4. 現(xiàn)場踩坑實錄與排查技巧4.1 比較器違約異常我第一次用 (a, b) - a[0] - b[0] 跑一個坐標很大的區(qū)間題時sort 直接拋了“Comparison method violates its general contract!”異常當時人都是懵的。后來才明白Java 的 TimSort 要求比較器滿足嚴格全序也就是自反、反對稱、傳遞三樣都要有。如果用減法比較一旦 a[0] 和 b[0] 逼近 int 的邊界a[0] - b[0] 溢出成負數(shù)就會產(chǎn)生“a 小于 bb 小于 c但 a 大于 c”這種矛盾排序算法沒法再繼續(xù)。解法非常簡單Integer.compare(a[0], b[0])。它內(nèi)部實現(xiàn)是 (x y) ? -1 : (x y ? 0 : 1)不會溢出且天然滿足傳遞性。不只這道題以后所有需要自定義比較器的題都建議默認使用 Integer.compare 或 Long.compare。這個習慣養(yǎng)成了基本能避開一大類詭異的排序 bug。4.2 最后一個區(qū)間總被漏掉“少一個區(qū)間”是合并區(qū)間最常見的高頻 bug。原因是這樣的掃描循環(huán)里每當遇到一個與當前區(qū)間斷開的區(qū)間你就把當前的 [curStart, curEnd] 存進結(jié)果然后開啟新的一段。循環(huán)結(jié)束后最后一個當前區(qū)間還沒被存必須手動補一次 merged.add({curStart, curEnd})。很多人寫著寫著就忘了這一行輸出結(jié)果永遠差一塊。怎么避免兩個辦法。第一把“提交當前區(qū)間”的代碼抽成一個 add 操作調(diào)試時在紙上標一個“循環(huán)結(jié)束后還要 add 一次”的鉤子。第二改用 ACwing 哨兵寫法用 st ! -2e9 判斷是否有待提交的區(qū)間循環(huán)統(tǒng)一處理后再補一次判斷從結(jié)構(gòu)上消滅遺漏。無論哪種核心是記住這個題一定會在循環(huán)外收尾。4.3 更新右端點時直接覆蓋我見過不止一次這種寫法if (intervals[i][0] curEnd) { curEnd intervals[i][1]; }問題我已經(jīng)在前面說過了。當新區(qū)間被當前區(qū)間完全包含時比如當前 [1,5]新來 [2,3]直接覆蓋會把 curEnd 從 5 改成 3把合并范圍回縮。更隱蔽的是如果后面接著一個 [3,4]用 3 去判斷 [3,4] 會被誤判為不重疊或重疊的分界結(jié)果不穩(wěn)定。這是一個典型的“單測數(shù)據(jù)恰好過了但邏輯卻錯了”的代碼。寫成 Math.max(curEnd, intervals[i][1]) 后這個場景就穩(wěn)了。排查這個問題的方法也簡單自己造幾個包含關(guān)系的用例比如 [[1,5],[2,3],[3,4]]跑一遍看輸出。4.4 重疊判斷的邊界語義“ 還是 ”這個一算子之差能直接改變答案。力扣 56 里 [1,2] 和 [2,3] 要合并所以不重疊判斷應(yīng)該是 merged[-1][1] interval[0]重疊判斷就是 interval[0] curEnd。如果你寫成 curEnd就會把這種端點相接的區(qū)間拆開少合并一對如果你在追擊問題時遇到“用最少的箭引爆氣球”這種題端點相接的氣球又算能被同一支箭引爆判斷邏輯仍然是相交時用 。反過來有些變體題定義“區(qū)間重疊”為真正的交集長度大于 0端點相接不算那就要用 判重疊。所以做題前第一件事是確認題目的重疊定義別想當然。注意如果你不確定題目里的“重疊”到底算不算端點相接先看輸入輸出示例。力扣 56 示例里 [1,3] 和 [2,6] 合并是因為有交集但真正暴露端點合并語義的用例是 [[1,2],[2,3]]輸出應(yīng)該只有一個 [1,3]。寫代碼前自己先跑一遍這個用例。5. 從模板題延伸一網(wǎng)打盡區(qū)間家族5.1 力扣57 插入?yún)^(qū)間力扣 57 給的是一個已經(jīng)有序且無重疊的區(qū)間列表讓你插入一個新的區(qū)間。最簡單的做法就是復(fù)用 56 的模板把 newInterval 加進 intervals排序后調(diào)用 merge一句話結(jié)束。這種解法在面試里能過但你要是真想練好區(qū)間題最好還是寫 O(n) 的三段式。思路是分三塊處理newInterval 左邊的、和 newInterval 相交的、newInterval 右邊的。左邊那些區(qū)間的右端點嚴格小于 newInterval 的左邊界直接加入結(jié)果所有與 newInterval 相交的區(qū)間把 newInterval 的左端點和右端點分別取 min 和 max 延展剩下的右邊區(qū)間原樣追加。三步完事無需求數(shù)組。我自己刷題時對這題的建議是先用 merge 模板拿分再手寫一遍三段式加深理解兩種做法都練。5.2 力扣452 用最少數(shù)量的箭引爆氣球452 題是合并區(qū)間非常好的對照題。每個氣球的直徑用一個區(qū)間表示一支箭扎在某個 x 坐標上所有包含這個 x 的區(qū)間都會爆。目標是用最少的箭也就是找最少的位置覆蓋所有區(qū)間。排序后維護的不是右端點最大值而是當前這組可一起引爆的氣球的公共右端點最小值。當新區(qū)間的起點大于當前公共右端點時說明前面這組必須單獨射一支箭了計數(shù)加一然后用新區(qū)間開啟新的一組。這個貪心里“公共區(qū)間必須非空”和合并區(qū)間“只要碰頭就能合并”是同一個判定系統(tǒng)的兩個方向把 56 練透了452 的代碼看一眼模板就能寫。5.3 力扣435 無重疊區(qū)間與1288 刪除被覆蓋區(qū)間435 題要求移除最少的區(qū)間使得剩下的區(qū)間互不重疊。經(jīng)典貪心是按終點升序排序然后盡可能多地保留區(qū)間維護上一個被保留區(qū)間的右端點遇到新區(qū)間起點大于等于它時保留否則丟棄。這個排序選擇正好和 56 相反因為這里要的是“盡快結(jié)束當前區(qū)間給后面留空間”。1288 題則要你刪除所有被其他區(qū)間覆蓋的區(qū)間。排序要寫成起點升序、終點降序起點相同讓較大的區(qū)間排在前面這樣掃描時一旦發(fā)現(xiàn)當前區(qū)間的右端點小于等于已經(jīng)覆蓋過的最遠右端點它一定是被覆蓋的可以刪除。這四道題算下來你會發(fā)現(xiàn)核心都是“排序確定貪心方向掃描維護一個關(guān)鍵區(qū)間”的模板區(qū)別只在維護的是最大值還是最小值、排序用的是起點還是終點。把 56 吃透等于拿到了整個區(qū)間家族的鑰匙。我個人刷這類模板題的習慣是第一遍看著模板默寫第二遍完全合上代碼手寫第三遍換一種語言再寫一遍。三遍下來合并區(qū)間這個套路基本就長在腦子里了后來面試遇到類似的題我甚至會先跟面試官說一句“這道題考排序我先按左端點排序再用兩個變量維護當前合并區(qū)間最后循環(huán)外補一次提交”對方通常都會點頭。如果你也在準備力扣熱題 100建議把這道題放在排序?qū)ｎ}的第一個去啃啃透它后面一串區(qū)間題都會順很多。別小看這種基礎(chǔ)模板題它才是真正能讓你在面試里穩(wěn)定拿分的底子。