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