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