刷算法題這幾年最怕看到兩類題一類是動態(tài)規(guī)劃狀態(tài)轉(zhuǎn)移方程搞死人另一類就是貪心思路看著挺對一提交就WA看完題解才發(fā)現(xiàn)自己漏了個反例。不過貪心里面有個很固定的套路就是“區(qū)間問題”。區(qū)間選點、最大不相交區(qū)間數(shù)量、區(qū)間分組、區(qū)間覆蓋這四個經(jīng)典模型幾乎每次筆試面試都會以某種變形出現(xiàn)。我把它們?nèi)看饋碇v一遍從貪心策略到正確性證明從C代碼到邊界細節(jié)一篇看懂四道題。1. 為什么算法題里總有“區(qū)間”的身影1.1 從生活中的調(diào)度說起假設你今天有五個會議要排每個會議有開始時間和結(jié)束時間你作為會議室的安排人員目標是用最少的會議室把會議全部安排下。這個場景抽象成數(shù)學語言就是N個區(qū)間[l_i, r_i]區(qū)間之間可能有重疊問至少需要幾個“容器”來裝這些重疊區(qū)間。這不就是開會排期嘛。類似的場景還有一臺機器加工多個任務每個任務占用的時間段互不重疊最多能安排幾個任務一條數(shù)軸上要放發(fā)射塔需要讓每段道路都被某個發(fā)射塔覆蓋最少放幾個塔這些場景的共同點就是輸入是一堆線段輸出是一個最優(yōu)數(shù)量。算法競賽和面試特別喜歡這類題因為區(qū)間題天然有實際背景代碼短但要想全對必須對貪心策略背后的邏輯有充分理解。1.2 四個問題其實是一個家族圍繞區(qū)間有四道非常經(jīng)典的貪心題區(qū)間選點給定N個區(qū)間選最少的點使得每個區(qū)間都至少包含一個點。最大不相交區(qū)間數(shù)量給定N個區(qū)間選盡量多的區(qū)間使得選出的區(qū)間兩兩不相交。區(qū)間分組給定N個區(qū)間把所有區(qū)間分成盡量少的組每組內(nèi)部的區(qū)間兩兩不相交。區(qū)間覆蓋給定一個目標線段[s, t]從N個區(qū)間里選盡量少的區(qū)間把目標線段完全覆蓋。這四道題看上去差別很大但底層用的都是“排序 掃描 貪心決策”這個框架。區(qū)別在于排序的鍵和掃描時的更新規(guī)則不同。如果能把四道題的異同講清楚之后遇到任何區(qū)間變形題你都能一眼看出它在考哪個模型。1.3 貪心算法的基礎思考方式貪心的核心就一句話不做全局規(guī)劃只看當前這一步選一個局部最優(yōu)的決策希望它能導出全局最優(yōu)。聽起來像廢話但在區(qū)間問題上貪心之所以成立是因為區(qū)間之間有種“排序后序貫決策”的特殊結(jié)構。你按某個端點排序后每次只需要關心當前狀態(tài)的一個邊界值不需要回頭看已經(jīng)處理完的區(qū)間。學習區(qū)間問題最好的方式是先理解貪心策略的“直覺”再用反證法或者替換法說服自己最后寫代碼驗證。千萬不要只會背代碼遇到變式照樣會翻車。2. 區(qū)間選點最少點覆蓋所有區(qū)間2.1 問題定義與最樸素的直覺給定N個閉區(qū)間[l_i, r_i]在數(shù)軸上放若干個點要求每個區(qū)間內(nèi)至少有一個點求點的最少數(shù)量。最樸素的想法是從左往右掃描遇到一個還沒被覆蓋的區(qū)間就在它的某個位置放一個點。問題是放在哪里直覺告訴你應該放在“盡量靠右”的位置因為越靠右越有可能順便覆蓋后面的區(qū)間。那么什么叫“盡量靠右”最靠右的位置就是當前區(qū)間的右端點。所以貪心策略出來了把所有區(qū)間按右端點從小到大排序依次掃描。如果當前區(qū)間的左端點大于上一個選擇的點的位置說明上一個點覆蓋不到它就選擇當前區(qū)間的右端點作為新點。2.2 貪心策略按右端點排序為什么要按右端點排序而不是按左端點排序這里有一個很經(jīng)典的反例區(qū)間1: [1, 10] 區(qū)間2: [2, 3]如果按左端點排序先處理[1,10]在右端點10放一個點然后區(qū)間[2,3]已經(jīng)被覆蓋結(jié)果用了1個點。但這樣其實“浪費了”放點的位置。我們再看一組區(qū)間A: [1, 5] 區(qū)間B: [2, 6] 區(qū)間C: [3, 4]如果按左端點排序選右端點第一個右端點是5覆蓋了A和BC還沒覆蓋所以再選C的右端點4一共2個點。但如果按右端點排序第一個右端點是4C然后A和B都包含4嗎A包含B不包含所以B需要再選一個點6共2個點。好像一樣。真正能體現(xiàn)右端點排序優(yōu)勢的是更長的例子[1, 2] [3, 5] [4, 6] [7, 9]按左端點排序第一個右端點2覆蓋[1,2]下一個[3,5]左端點32選右端點5覆蓋[3,5]和[4,6]下一個[7,9]左端點75選右端點9。共3個點。 按右端點排序[1,2]右端點2覆蓋它[3,5]右端點5選點5同時覆蓋[4,6][7,9]選點9。也是3個點好像結(jié)果一樣。其實這兩個策略在很多常規(guī)數(shù)據(jù)下結(jié)果相同但右端點排序有嚴格的正確性保證而左端點排序在某些特殊構造下會出錯。我記得有一個經(jīng)典反例[1, 3] [2, 5] [4, 6]左端點排序第一個右端點3覆蓋[1,3]和[2,5][4,6]左端點43選右端點6。共2個點。 右端點排序第一個右端點3覆蓋[1,3]和[2,5][2,5]包含3覆蓋[4,6]不包含3選6。共2個點結(jié)果一樣?？雌饋碜蠖它c排序在這個例子里也沒問題但左端點排序在這個方向上不存在嚴格證明。網(wǎng)上很多資料直接用“按右端點排序”因為它有替換法證明而左端點排序只能碰運氣。實際寫代碼時按右端點排序才是最穩(wěn)妥的選擇。2.3 正確性證明思路這個證明可以用替換法。假設貪心算法選出的點集是G {g1, g2, ..., gk}最優(yōu)解的點集是O {o1, o2, ..., om}其中m是最少點數(shù)。我們要證明k m。關鍵在于證明貪心選擇的每個點的位置都不比最優(yōu)解對應順序中的點更靠左。具體地第一個貪心點g1一定是右端點最小的那個區(qū)間的右端點而最優(yōu)解中覆蓋這個區(qū)間的點o1不可能比g1更靠右因為是覆蓋該區(qū)間的最優(yōu)解該點必須落在區(qū)間內(nèi)而該區(qū)間右端點最小所以o1 ≤ g1也就是g1不會比o1更靠左。然后用歸納法處理完第i個點時貪心選擇的點位置g_i不早于最優(yōu)解中對應的o_i。既然貪心點不落后那么貪心選完第i個點后剩余待覆蓋的區(qū)間集合不會比最優(yōu)解處理完第i個點后更多。所以貪心不會比最優(yōu)解使用更多點。反過來最優(yōu)解是最少的所以兩者相等。這個證明思路很重要因為后面最大不相交區(qū)間數(shù)量、區(qū)間覆蓋也會用到類似的替換法。2.4 C代碼實現(xiàn)與踩坑點直接看代碼#include iostream #include algorithm using namespace std; const int N 100010; struct Range { int l, r; bool operator (const Range W) const { return r W.r; } } range[N]; int main() { int n; scanf(%d, n); for (int i 0; i n; i) scanf(%d%d, range[i].l, range[i].r); sort(range, range n); int cnt 0; int last -2e9; for (int i 0; i n; i) { if (range[i].l last) { cnt; last range[i].r; } } printf(%d\n, cnt); return 0; }有幾個細節(jié)容易踩坑last初始值要設成一個極小數(shù)比如-2e9不能設0因為區(qū)間端點可能是負數(shù)。判斷條件是range[i].l last不是。因為兩個閉區(qū)間如果只在端點相碰點放在端點上可以同時覆蓋兩個區(qū)間。比如[1,2]和[2,5]在2放一個點就都覆蓋了。如果你用會認為[2,5]沒被覆蓋結(jié)果多放一個點WA。如果區(qū)間是左閉右開的[l, r)判斷條件要改成range[i].l last因為此時端點處不算覆蓋。做題時先看清楚題目說的是閉區(qū)間還是開區(qū)間人家挖的坑就在這。2.5 示例數(shù)據(jù)手工推導我準備一組樣例5 1 3 2 5 3 6 4 7 6 8按右端點排序后是[1,3] [2,5] [3,6] [4,7] [6,8]初始last -∞第一個區(qū)間[1,3]1 -∞放點3last 3。[2,5]2 3不成立所以跳過。[3,6]3 3不成立跳過。注意區(qū)間[3,6]包含點3所以確實不用新點。[4,7]4 3放點7last 7。[6,8]6 7不成立跳過。答案是2個點分別是3和7。手工推一遍就能理解為什么判斷條件是嚴格大于。3. 最大不相交區(qū)間數(shù)量邊貪心邊證明3.1 問題背景與貪心策略給定N個區(qū)間選出盡可能多的區(qū)間使它們兩兩不重疊端點重合視情況一般算作不相交。這個問題的貪心策略和區(qū)間選點一模一樣按右端點排序然后從左到右掃描。如果當前區(qū)間的左端點大于等于上一個選中區(qū)間的右端點就選擇當前區(qū)間并更新右端點為當前區(qū)間的右端點。這個策略的直覺是為了給后面的區(qū)間留出更多空間我們應該選擇結(jié)束時間更早的區(qū)間。就像一個人一天要趕很多場活動每一場都選最早結(jié)束的那個就能參加最多的場次。3.2 為什么與區(qū)間選點是“孿生兄弟”如果你已經(jīng)寫過區(qū)間選點的代碼你會發(fā)現(xiàn)最大不相交區(qū)間數(shù)量的代碼幾乎一模一樣只是比較條件從l last換成了l last因為要保證兩個閉區(qū)間沒有公共點。這不是巧合這兩個問題在數(shù)學上是對偶的。區(qū)間選點要求用最少的點打中所有區(qū)間而最大不相交區(qū)間要求選出最多互不重疊的區(qū)間。你選出的每一個點都可以對應一組被它覆蓋的、互不重疊的、在數(shù)軸上從左到右排列的區(qū)間。反過來一組互不重疊的區(qū)間每個區(qū)間至少需要一個不同的點來覆蓋。所以最少點數(shù) 最大不相交區(qū)間數(shù)量。很多教材里會專門講這個等價關系理解了它兩道題能同時記住。3.3 代碼實現(xiàn)#include iostream #include algorithm using namespace std; const int N 100010; struct Range { int l, r; bool operator (const Range W) const { return r W.r; } } range[N]; int main() { int n; scanf(%d, n); for (int i 0; i n; i) scanf(%d%d, range[i].l, range[i].r); sort(range, range n); int cnt 0; int last -2e9; for (int i 0; i n; i) { if (range[i].l last) { cnt; last range[i].r; } } printf(%d\n, cnt); return 0; }3.4 端點相撞到底算不算重合這里有一個非常容易在面試里被追問的點如果兩個區(qū)間是[1,2]和[2,3]它們算不算不相交在數(shù)學的閉區(qū)間定義里它們確實有一個公共點2所以是“相交”的。但在算法題約定里很多題目會規(guī)定“端點重合不算相交”或者“區(qū)間之間可以有公共端點”。這類題目你必須在開頭就假設好比較時用l last允許端點重合還是l last不允許端點重合。如果題目說“區(qū)間之間不能有公共點”那就用。如果題目說“端點重合不影響”那就用。純靠記憶不行要能根據(jù)題目描述現(xiàn)場判斷。實測中大部分區(qū)間問題的經(jīng)典模板默認端點重合不算沖突也就是用所以初學時按這個來就行但做題時還是要看題目要求。補充一個例子驗證一下貪心選擇確實是正確的4 [1, 2] [2, 3] [3, 4] [1, 3]按右端點排序后是[1,2]、[2,3]、[3,4]、[1,3]排序時[1,3]右端點3要放在[3,4]前面所以順序是[1,2]、[2,3]、[1,3]、[3,4]。掃描過程選[1,2]last 2。[2,3]2 2成立選它last 3。[1,3]1 3不成立跳過。[3,4]3 3成立選它last 4。答案是3。你可以自己試試是不是沒有其他方案能選到4個區(qū)間這就是貪心給出的最優(yōu)解。4. 區(qū)間分組讓互不相交的區(qū)間待在一起4.1 問題和貪心策略區(qū)間分組是這四道題里“畫風”最不一樣的一道。它的目標是把所有區(qū)間分成最少的若干組每組內(nèi)的區(qū)間兩兩互不相交。舉個例子假設有5個區(qū)間[1, 3] [2, 4] [3, 5] [4, 6] [5, 7]這幾個區(qū)間每個都和相鄰的重疊肉眼可見至少需要3組[1,3][3,5][5,7]端點重合視為不相交是一組[2,4][4,6]是一組但[2,4]和[3,5]有重疊所以要另起一組看起來正好3組能裝下。貪心策略按左端點從大到小排序其實就是升序掃描每個區(qū)間嘗試把它放進某個已有的組。關鍵問題是怎么知道它能放進哪個組答案是維護每個組當前最后一個區(qū)間的右端點。如果當前區(qū)間的左端點大于某個組的最后右端點說明它和這個組最后一個區(qū)間不相交可以放進這個組。由于我們只需要判斷“有沒有一個組能放下”而不是具體哪個組所以用小根堆維護所有組的右端點取最小的那個看能不能放。4.2 小根堆維護每個組的右端點為什么只要看最小右端點的組因為貪心策略下所有組的右端點都可以看成“最緊張的那個狀態(tài)”。如果當前區(qū)間的左端點比最小的右端點還小說明它和每個組都有重疊那必然要新開一組。如果它大于等于最小右端點那至少和右端點最小的那個組不重疊直接放進那個組即可。注意這里比較的是heap.top() range[i].l還是heap.top() range[i].l取決于“端點重合是否允許放同一組”。經(jīng)典模板默認允許端點在同一個點上也就是heap.top() range[i].l時放入否則新開組。如果你遇到題目說左右端點不能相碰就改成heap.top() range[i].l。這個“看最小右端點”的思路特別像在窗口排隊每隊最后一個人辦完業(yè)務的時間最早結(jié)束的隊伍最空新來的人只要比那個時間晚到就能排到那一隊。4.3 正確性證明思路這個證明常用反證法。假設貪心算法在第i步不得不開新組而最優(yōu)解此時不需要開新組也就是說當前區(qū)間與最優(yōu)解中每組最后一個區(qū)間都不相交。但貪心選擇的是所有組里右端點最小的那個如果當前區(qū)間與這個最小的有重疊那它與所有組的最后一個區(qū)間都有重疊因為其他組的右端點更大矛盾。這正是“鴿巢原理”式的論證如果重疊度足夠高你不可能不新開一組。從另一個角度說區(qū)間分組的最少組數(shù)實際上等于數(shù)軸上某個時刻最多有多少個重疊區(qū)間同時存在。因為重疊在同一時刻的區(qū)間必須分到不同組所以組數(shù)至少等于重疊的最大深度而按左端點排序掃描時貪心恰好能構造出這個最大深度那么多個組。這兩個觀點殊途同歸。4.4 代碼實現(xiàn)與邊界#include iostream #include algorithm #include queue using namespace std; const int N 100010; struct Range { int l, r; bool operator (const Range W) const { return l W.l; } } range[N]; int main() { int n; scanf(%d, n); for (int i 0; i n; i) scanf(%d%d, range[i].l, range[i].r); sort(range, range n); priority_queueint, vectorint, greaterint heap; for (int i 0; i n; i) { auto t range[i]; if (!heap.empty() heap.top() t.l) { heap.pop(); heap.push(t.r); } else { heap.push(t.r); } } printf(%d\n, (int)heap.size()); return 0; }注意幾個邊界點priority_queue默認是大根堆要用greaterint讓它變成小根堆。heap.top() t.l是判斷可不可以放入如果堆頂?shù)扔诋斍白蠖它c而且題目不允許端點重合要改成heap.top() t.l。如果新開了組直接push(t.r)組的數(shù)量最終等于堆的大小。每組內(nèi)區(qū)間是按左端點遞增處理的所以放進去時只需保存該組最新右端點。手工推剛才那組樣例5 1 3 2 4 3 5 4 6 5 7按左端點排序后不變。前三個區(qū)間[1,3]、[2,4]、[3,5]第一個直接放一組堆為{3}第二個左端點2堆頂33 2不成立開新組堆為{3,4}第三個左端點3堆頂33 3不成立開新組堆為{3,4,5}。第四個[4,6]左端點4堆頂33 4成立彈出3壓入6堆為{4,5,6}。第五個[5,7]左端點5堆頂44 5成立彈出4壓入7堆為{5,6,7}。組數(shù)是3正確。4.5 換一種無堆解法差分數(shù)組區(qū)間分組的本質(zhì)是求“最大重疊層數(shù)”這個結(jié)論可以換個角度理解把每個區(qū)間看成一條線段記錄數(shù)軸上每個位置被多少個區(qū)間覆蓋覆蓋次數(shù)的最大值就是最少組數(shù)。因為同一時間重疊在一起的所有區(qū)間必須各占一組。那么可以用差分數(shù)組做。比如所有端點范圍在1e6以內(nèi)for (int i 0; i n; i) { diff[l]; diff[r]--; }然后前綴和求最大值。但注意閉區(qū)間端點的處理要小心如果區(qū)間在l處開始、r處結(jié)束覆蓋位置是[l, r]我們可以在l處加1在r1處減1。但前提是坐標范圍不大。這個方法的復雜度是O(坐標范圍 n)在坐標范圍大的時候不如排序堆的做法通用。所以競賽里推薦用堆的方法差分數(shù)組適合當作一條思維擴展來理解。5. 區(qū)間覆蓋用最少的區(qū)間拼出一條通路5.1 問題描述與貪心策略第四次變復雜了一點給定一個目標區(qū)間[s, t]以及N個可選區(qū)間要求從N個區(qū)間里選出盡可能少的區(qū)間使得這些區(qū)間的并集完全覆蓋[s, t]。如果不能覆蓋輸出-1。貪心策略是把所有區(qū)間按左端點排序從左往右掃描每次從所有能覆蓋當前起點start的區(qū)間中選擇一個右端點最遠的區(qū)間然后更新start為這個右端點。重復這個過程直到start t或者找不到可選區(qū)間。為什么選右端點最遠的和區(qū)間選點選右端點的理由一樣越往后延展越遠越省區(qū)間數(shù)。把這個問題想成鋪路你從位置start出發(fā)面前有一些磚頭區(qū)間每塊磚頭必須蓋住你腳下的位置才能用。在能用的一堆磚頭里當然選最長的那塊鋪出去最遠這樣剩下的路最短。5.2 貪心過程詳解實現(xiàn)上有一個很典型的雙指針技巧我單獨拆開講。先排序所有區(qū)間按左端點升序排。維護一個指針i從頭掃描。每一輪循環(huán)找所有l(wèi) start的區(qū)間更新max_r max(max_r, r)。如果max_r start說明存在一段空隙沒有任何區(qū)間能覆蓋start直接返回-1。區(qū)間數(shù)加1把start max_r。如果start t結(jié)束。關鍵點第1步里的循環(huán)不能每次都從頭開始因為之前的區(qū)間已經(jīng)被處理過。用一個全局指針i每一輪從當前i開始向后掃凡是l start的都參與更新遇到第一個l start就停止進入下一輪。5.3 代碼實現(xiàn)與斷檔處理#include iostream #include algorithm using namespace std; const int N 100010; struct Range { int l, r; bool operator (const Range W) const { return l W.l; } } range[N]; int main() { int s, t; scanf(%d%d, s, t); int n; scanf(%d, n); for (int i 0; i n; i) scanf(%d%d, range[i].l, range[i].r); sort(range, range n); int cnt 0; bool success false; int i 0; while (i n) { int max_r -2e9; while (i n range[i].l s) { max_r max(max_r, range[i].r); i; } if (max_r s) break; // 斷檔 cnt; if (max_r t) { success true; break; } s max_r; } if (!success) printf(-1\n); else printf(%d\n, cnt); return 0; }這里有個隱藏很深的bug內(nèi)層while結(jié)束后i指向的是第一個l s的區(qū)間下一輪外層循環(huán)不會重復訪問已經(jīng)遍歷過的區(qū)間這是正確的。但要注意當max_r t時break前必須把success置為true否則循環(huán)結(jié)束條件是i n時也可能誤判為失敗。5.4 手算示例假設[s,t] [1, 5]區(qū)間是4 [1, 2] [2, 4] [3, 6] [4, 5]排好序后直接掃描。第一輪start 1所有l(wèi) 1的只有[1,2]max_r 2。cnt 1s更新為2。第二輪start 2所有l(wèi) 2的有[2,4]max_r 4。cnt 2s 4。第三輪start 4所有l(wèi) 4的有[3,6]和[4,5]max_r 6cnt 36 5成功。答案是3。當然如果區(qū)間[3,6]能直接覆蓋到6那確實第2輪的時候就應該被選上為什么第二輪沒有選它因為在第二輪開始時start 2而[3,6]的左端點3 2它覆蓋不住當前位置2不能“抬腳”從2開始鋪。這就是“必須覆蓋當前起點”的約束。6. 四個問題的橫向?qū)Ρ扰c思維工具6.1 一張表看懂四個策略問題名稱排序方式掃描/更新規(guī)則關鍵數(shù)據(jù)結(jié)構區(qū)間選點按右端點升序l last時選點更新last為該區(qū)間右端點變量last最大不相交區(qū)間按右端點升序l last時選取更新last為該區(qū)間右端點變量last區(qū)間分組按左端點升序堆頂 l則放入該組否則開新組小根堆維護各組右端點區(qū)間覆蓋按左端點升序每輪找所有l(wèi) start區(qū)間取最大右端點更新start雙指針 變量一眼看過去選點和最大不相交的排序鍵一樣更新規(guī)則只差一個等號分組和覆蓋都用左端點排序但分組用堆處理“并行容器”覆蓋用雙指針處理“串聯(lián)推進”。這是它們最核心的區(qū)別。6.2 什么時候用右端點什么時候用左端點判斷依據(jù)不是死記硬背而是看問題的時間方向。如果想讓“讓后面的區(qū)域更自由”你自然希望當前選中的區(qū)間結(jié)束得盡可能晚或早選點和最大不相交問題中核心矛盾是“一個點/區(qū)間和后面區(qū)間是否沖突”因此按右端點排序讓最緊迫的區(qū)間先決策。分組和覆蓋問題中核心矛盾是“起點固定能延伸多遠”因此按左端點排序從左邊開始逐步推進每一步貪心地延伸最遠。用生活類比如果是在一天內(nèi)安排活動優(yōu)先選最早結(jié)束的右端點排序如果要鋪一條路從左往右優(yōu)先選能鋪最遠的那塊“磚”左端點排序。這個直覺能幫你應對很多變式題。6.3 貪心的常見誤區(qū)誤區(qū)一貪心不證明直接寫代碼。區(qū)間題的正確性證明并不難熟練之后五分鐘能寫完但跳過的后果是遇到刁鉆數(shù)據(jù)WA到懷疑人生。誤區(qū)二端點等號搞錯。閉區(qū)間和開區(qū)間、允許端點重合和不允許端點重合在四道題里分別對應不同的比較符號。一題之差可能就是WA。誤區(qū)三區(qū)間覆蓋里忘記更新起點或者死循環(huán)。雙指針如果指針沒有推進內(nèi)層循環(huán)會無限跑。寫完之后用隨機數(shù)據(jù)對拍是排查這類問題的好方法。7. 實戰(zhàn)中的細節(jié)與擴展7.1 輸入輸出與調(diào)試經(jīng)驗很多人覺得區(qū)間題代碼短不需要調(diào)試其實這是個誤區(qū)。我寫區(qū)間題最容易出錯的點有三個第一結(jié)構體運算符重載寫錯。如果從小到大排序operator里返回的是r W.r還是W.r r自己也容易繞進去。如果你不想重載可以這樣寫sort(range, range n, [](const Range a, const Range b) { return a.r b.r; });lambda表達式更直白不容易出錯。第二last初始化用-2e9而不是0。很多題目坐標可以是負數(shù)用0會導致初始判斷出錯。第三區(qū)間覆蓋里內(nèi)層循環(huán)的i指針容易失控。建議每次更新max_r后先打印一次i、s、max_r確認指針沒有跳過頭。7.2 數(shù)據(jù)范圍與復雜度的關系四個問題的時間復雜度都是O(n log n)主要瓶頸在排序?？臻g復雜度是O(n)。當n達到1e5或者1e6時這個復雜度完全沒問題。但如果你用差分數(shù)組做區(qū)間分組復雜度會變成O(坐標范圍 n)坐標范圍小的時候更快但坐標范圍1e9時就爆了所以競賽里排序堆的做法更保險。還有一個值得注意的點區(qū)間選點和最大不相交區(qū)間數(shù)量在n很大而坐標范圍很小的時候其實也可以轉(zhuǎn)換成差分題不過意義不大。作為算法學習者優(yōu)先掌握排序 貪心這套通法。7.3 類似變式帶權區(qū)間調(diào)度、最少箭頭戳破氣球經(jīng)典區(qū)間題的價值在于它可以變形出很多高級題。我自己遇到過的兩個典型變式帶權區(qū)間調(diào)度每個區(qū)間除了左右端點還有一個權重要選一組互不相交的區(qū)間使總權重最大。這個問題貪心解決不了因為局部“最早結(jié)束”不保證權重最大需要按右端點排序后用動態(tài)規(guī)劃。轉(zhuǎn)移方程很簡單dp[i] max(dp[i-1], dp[p] w[i])其中p是第i個區(qū)間之前最后一個不與它重疊的區(qū)間下標二分查找優(yōu)化到O(n log n)。最少箭頭戳破氣球LeetCode 452其實就是區(qū)間選點的換皮題。氣球是區(qū)間箭頭是點一支箭可以射穿多個重疊區(qū)間的公共位置求最少箭數(shù)。它和區(qū)間選點完全等價有些版本甚至不強調(diào)“選點”而是說“引爆氣球”。遇到這種題你只要能認出區(qū)間模型代碼幾乎是模板級別的。還有一類“會議安排”變式給你一堆會議時間問最多能參加幾個會議這就是最大不相交區(qū)間數(shù)量。而“最少會議室數(shù)量”則是區(qū)間分組。同一個生活場景換一個問法就是兩套完全不同的問題本質(zhì)都是區(qū)間貪心。8. 個人經(jīng)驗收尾這套區(qū)間問題我前前后后寫過不下二十遍每次面試前還會重新手推一遍證明。我最大的體會是學區(qū)間題不能只記“按右端點排序”這個口訣而是要理解排序之后為什么掃描過程能得到全局最優(yōu)。另外一個小技巧把四道題的代碼模板整理到一個文件里只改排序鍵和判斷條件每次寫新題時對照“它到底是選點、選區(qū)間、分組還是覆蓋”然后套模板再根據(jù)題目要求調(diào)整等號。這套流程熟練之后這類題基本是送分題。還有一個建議練習時不要只刷通過可以嘗試用隨機數(shù)據(jù)生成器對拍。比如自己寫一個暴力DFS求最優(yōu)解再和貪心跑出來的結(jié)果對比能幫你快速發(fā)現(xiàn)那些藏在角落里的反例。我之前就是靠對拍才發(fā)現(xiàn)區(qū)間覆蓋里指針推進有問題。希望這篇總結(jié)能幫你在面試和競賽里穩(wěn)穩(wěn)拿下區(qū)間題。如果后續(xù)你遇到某個區(qū)間問題的奇怪變式就用這篇文章里的“問題分類 貪心策略 證明 代碼”四步法去拆解應該能少走不少彎路。