【正文】 1 淺談信息學(xué)競賽中的區(qū)間問題 華東師大二附中 周小博 【摘要】 本文對一些常用的區(qū)間問題模型做了簡單介紹，包括一些算法及其正確性的證明，并從國際、國內(nèi)的信息學(xué)競賽與大學(xué)生程序設(shè)計(jì)競賽中選了近 10 道相關(guān)例題，進(jìn)行簡要分析。 【關(guān)鍵字】 區(qū)間模型 轉(zhuǎn)化 貪心 動態(tài)規(guī)劃 優(yōu)化 2 【引言】 在信息學(xué)競賽中，有很多問題最終都能轉(zhuǎn)化為區(qū)間問題：例如從若干個區(qū)間中選出一些滿足一定條件的區(qū)間、將各個區(qū)間分配到一些資源中、或者將一些區(qū)間以某種順序放置等。這類問題變化繁多，解法各異，需要用到貪心、動態(tài)規(guī) 劃等算法，并可以用一些數(shù)據(jù)結(jié)構(gòu)優(yōu)化算法。 本文將從幾個方面對區(qū)間問題做一個簡單的介紹，給出一些算法及其正確性的證明，具體分如下幾個方面進(jìn)行討論： 、覆蓋問題 我們將對上述每個問題都給出基本模型、算法、證明及其實(shí)現(xiàn)，并從 ACMICPC、 CEOI、 CTSC 等比賽中選出了近 10 道相關(guān)例題，進(jìn)行簡要分析，有的例題還給出了各種不同的算法及其時間效率的分析。 本文中所討論的問題主要 由兩個部分組成，一部分為近幾年來各類競賽題的歸納總結(jié)，另一部分來自于參考文獻(xiàn)。 3 【正文】 數(shù)軸上有 n 個區(qū)間，選出最多的區(qū)間，使得這些區(qū)間不互相重疊。 算法： 將所有區(qū)間按右端點(diǎn)坐標(biāo)從小到大排序，順序處理每個區(qū)間。如果它與當(dāng)前已選的所有區(qū)間都 沒有重疊 ，則選擇該區(qū)間，否則不選。 證明： 顯然，該算法最后選出的區(qū)間 不互相重疊 ，下面證明所選出 區(qū)間的數(shù)量是最多的。 設(shè) if 為該算法所接受的第 i 個區(qū)間的右端點(diǎn)坐標(biāo)， ig 為某最優(yōu)解中的第 i 個區(qū)間的右端點(diǎn)坐標(biāo)。 命題 當(dāng) 1?i 時，該算法所接受的第 i 個區(qū)間的右端點(diǎn)坐標(biāo) if ≤某最優(yōu)解中的第 i 個區(qū)間的右端點(diǎn)坐標(biāo) ig 。 該命題 可以運(yùn)用數(shù)學(xué)歸納法來證明。對于 1?i ，命題顯然為真，因?yàn)樗惴ǖ谝粋€選擇的區(qū)間擁有最小右端點(diǎn)坐標(biāo)。令 1?i ，假定論斷對 1?i 為真，即 11 ?? ? ii gf 。則最優(yōu)解的第 i 個可選區(qū)間所組成的集合包含于執(zhí)行該算法時第 i 個可選區(qū)間所組成的集合；而當(dāng)算法選擇第 i 個區(qū)間時，選的是在可選區(qū)間中右端點(diǎn)坐標(biāo)最小的一個，所以有 ii gf ? 。證畢。 設(shè)該算法選出了 k 個區(qū)間，而最優(yōu)解選出了 m 個區(qū)間。 命題 最優(yōu)解選出的區(qū)間數(shù)量 m =該算法選出的區(qū)間數(shù)量 k 。 假設(shè) km? ，根據(jù)命題 ，有 kk gf ? 。由于 km? ，必然存在某區(qū)間，在 kg之后開始，故也在 kf 之后開始。而該算法一定不會在選了第 k 個區(qū)間后停止，還 4 會選擇更多的區(qū)間，產(chǎn)生矛盾。所以 km? ,又因?yàn)?m 是最優(yōu)解選出區(qū)間個數(shù)，所以 km? 。 綜上所述，算法選出的區(qū)間是最優(yōu)解。 實(shí)現(xiàn)： 在判斷某個區(qū)間與當(dāng)前已選的所有區(qū)間是否重疊時 ,可以直接判斷是否和所選的最后一個區(qū)間是否重疊。時間復(fù)雜度：排序 ? ?nnO log +掃描 ??nO = ? ?nnO log 。 例題 1： Latin America South America 2022 Problem A 題目大意： 基因是由許多外顯子（ exon）組成， 每個外顯子都有一個起始位置和一個結(jié)束位置。兩個外顯子能夠互相聯(lián)接必須滿足某個外顯子的起始位置在另一個外顯子的結(jié)束位置之后。給出 ? ?10000 ?? nn 個外顯子，要求找到一條由外顯子組成的基因鏈，使得外顯子數(shù)量最多。 分析： 將每個 外顯子看作一個區(qū)間，兩端點(diǎn)坐標(biāo)分別為外顯子的起始、結(jié)束位置。則現(xiàn)在的問題和原問題基本相同 ，只是端點(diǎn)上也不能重疊。這里就不寫算法了。 有 n 個區(qū)間和無限多的資源，每個資源上的區(qū)間之間不互相重疊 。將每個區(qū)間都分配到某個資源中，使用到的資源數(shù)量最小。 定義區(qū)間集合深度 d 為包含任意一點(diǎn)的區(qū)間數(shù)量的最大值，則顯然有： 命題 需要的資源數(shù)至少為 d 。 5 設(shè)區(qū)間 1I ,2I ,? ,dI 全部包含某一點(diǎn)，則必須把這些區(qū)間分配到不同資源中，故至少需要 d 個資 源。 其實(shí)競賽中也出現(xiàn)過計(jì)算區(qū)間集合深度的題目，如 North America – Northeast 2022 Problem E。下面給出計(jì)算區(qū)間集合深度的算法。 d 的計(jì)算方法： 將每個區(qū)間拆成兩個事件點(diǎn)，按坐標(biāo)從小到大排序， 順序處理每個區(qū)間 。記錄一個值 t ，表示當(dāng)前點(diǎn)被包含次數(shù)。每次遇到區(qū)間的左端點(diǎn)就 +1，遇到右端點(diǎn)就 1。 d 的值就是在該過程中 t 的最大值。注意兩個相同坐標(biāo)不同類型的事件點(diǎn)的位置關(guān)系和區(qū)間是否能在端點(diǎn)處重疊有關(guān)，這在排序過程中應(yīng)該注意。時間復(fù)雜度為 排序 ? ?nnO log +掃描 ??nO = ? ?nnO log 由此可得出一個構(gòu)造算法。 算法 1： 計(jì)算出 d 。將所有區(qū)間按左端點(diǎn)坐標(biāo)從小到大排序，順序處理每個區(qū)間。處理某個區(qū)間 時，排除 在它前面且與之重疊的區(qū)間所用到的資源，然后在1,2,3,? ,d 這些資源中任意分配一個未被排除的資源。 證明： 設(shè)排序后的 n 個區(qū)間分別為 1I ,2I ,? ,nI 命題 每個區(qū)間都能分配到一個資源。 考慮任何一個區(qū)間 jI ，假設(shè)存在 t 個區(qū)間在它前面且與之重疊。一定有dt ??1 ，否則由于這 1?t 個區(qū)間都包含 jI 的起始時刻，與 d 的定義矛盾。故有1??dt ，從而在 d 個資源中至少有一個資源沒被這 t 個區(qū)間排除。所以對于每個 6 區(qū)間，都至少 有一個可分配資源。證畢。 命題 沒有兩個互相重疊的區(qū)間被分配到了同一個資源。 考慮任意兩個互相重疊的區(qū)間1jI、2jI，其中 21 jj? 。當(dāng)算法在處理區(qū)間2jI時，區(qū)間1jI所用資源已經(jīng)被排除，所以不會被分配到同一資源。 綜上所述，該算法可以成功的構(gòu)造出正好使用 d 個資源的一組解，而根據(jù)命題 ，所用資源的下限是 d ，故該解是用到資源數(shù)量最少的解。 實(shí)現(xiàn)： 區(qū)間分配資源時，如果直接做排除，則時間復(fù)雜度為 ? ?2nO ，當(dāng)然可以通過記錄每個資源的最大右端點(diǎn)坐標(biāo)以將時間復(fù)雜度降為 ? ?ndO ；由于可以每次找一個最大右端點(diǎn)坐標(biāo)最小的資源，故可以用一個優(yōu)先隊(duì)列來儲存每個資源的最大右端點(diǎn)坐標(biāo)。 用二叉堆實(shí)現(xiàn)該優(yōu)先隊(duì)列，每次查找最小值的時間復(fù)雜度為 ??1O ，修改關(guān)鍵字的時間復(fù)雜度為 ? ?dOlog ， 分配資源操作的時間復(fù)雜度也就降為 ? ?dnO log 。故總 時 間 復(fù) 雜 度 為 ： d 的計(jì)算 ? ?nnOlog + 排序 ? ?nnOlog + 分配資源? ?dnO log = ? ?? ?ndnO log 。其實(shí)這里可以不計(jì)算出 d ，而通過不斷地增加資源數(shù)量來使所有區(qū)間都能分配到資源。 該算法同時也證明了以下命題： 命題 用到的資源數(shù)量的最小值為區(qū)間集合深度 d 。 基于這個命題，我們很容易想到另外一種算法。 7 算法 2： 計(jì)算 d 。將所有區(qū)間按右端點(diǎn)坐標(biāo)從小到大排序，順序處理每個區(qū)間。對于每個區(qū)間，都在 1,2,3,? ,d 這些資源中 分配一個可用的且右端點(diǎn)坐標(biāo)最大的資源。 證明： 顯然每個資 源上的區(qū)間都不互相重疊，下面證明每個區(qū)間都能分配到一個可用資源。用一個元素個數(shù)為 d 的有序表 iS （表中元素始終從小到大排序），記錄處理 i 個區(qū)間后，各個資源的 最大右端點(diǎn)坐標(biāo) （當(dāng)某個資源從沒被用過時，可認(rèn)為值為 ?? ）。同樣用表 iS? 表示處理 i 個區(qū)間后，某最優(yōu)解的 狀態(tài)（根據(jù)命題 ，該表中元素個數(shù)也是 d ）。狀態(tài) iS? 不優(yōu)于 iS 狀態(tài)指 ? ? ? ?jSjSdj ii ????? ,1 。 命題 處理完第 ? ?1?ii 個區(qū)間后，某最優(yōu)解此時的狀態(tài) iS? 不優(yōu)于運(yùn)行該算法后此時的狀態(tài) iS 。 該命題可以運(yùn)用數(shù)學(xué)歸納法來證明。對于 1?i ，命題顯然為真，因?yàn)榈谝粋€區(qū)間無論分配哪個資源，狀態(tài)都是一樣的。令 1?i ，假定論斷對 1?i 為真，即? ? ? ?jSjSdj ii 11,1 ?? ????? 。設(shè)處理第 i 個區(qū)間時，該算法分配的資源是 ? ?11 jSi? ,在最優(yōu)解中分配的資源為 ? ?21 jSi? 。設(shè)第 i 個區(qū)間的右端點(diǎn)坐標(biāo)為 ??ie 。 表 iS 更新為： ? ? ? ? ? ? ? ? ? ? ? ? ? ?? ?iedSjSjSjSSS iiiiii ,1,2,1,1,2,1 111111111 ?????? ?????? ； 表 iS? 更新為： ? ? ? ? ? ? ? ? ? ? ? ? ? ?? ?iedSjSjSjSSS iiiiii ,1,2,1,1,2,1 121212111 ???????????? ?????? 。 而該算法分配的資源 ? ?11 jSi? 在所有可分配資源中擁用最大右端點(diǎn)坐標(biāo)，故區(qū)間 i 的左端點(diǎn)坐標(biāo)小于 ? ?111 ?? jSi ，又 ? ? ? ?11 1111 ???? ?? jSjS ii ，所以 12 jj ? 。 ⑴當(dāng) 21 jj?? 時： ? ? ? ? ? ? ? ?jSjSjSjS iiii ????? ?? 11 ； ⑵當(dāng) 12 jjj ?? 時： ? ? ? ? ? ? ? ? ? ?jSjSjSjSjS iiiii ???????? ??? 1111 ； 8 ⑶當(dāng) djj ??1 時： ? ? ? ? ? ? ? ?jSjSjSjS iiii ??????? ?? 11 11 ； ⑷當(dāng) dj? 時： ? ? ? ? ? ?iejSjS ii ??? 。 所以有 ? ? ? ?jSjSdj ii ????? ,1 ，證畢。 命題 每個區(qū)間都能分配到一個資源。 處理第 i 個區(qū)間時，狀態(tài)可用 1?iS 表示。最優(yōu)解肯定能給該區(qū)間分配到資源，設(shè)為 ? ?01 jSi?? 。根據(jù)命題 ， ? ? ? ?0101 jSjS ii ?? ?? 。則運(yùn)行該算法時，至少可以給該區(qū)間分配資源 ? ?01 jSi? 。證畢。 綜上所述，該算法可以成功的構(gòu)造出正好 使用 d 個資源的一組解，而根據(jù)命題 d ，故該解是用到資源數(shù)量最少的解。 實(shí)現(xiàn)： 考慮如何 分配資源。如果直接記錄每個資源的最大右端點(diǎn)坐標(biāo)，時間復(fù)雜度為 ? ?ndO ?？梢杂米C明中所提到的有序表，用一個平衡二叉樹來維護(hù)它。每次處理某個 區(qū)間 時，可以在 ? ?dOlog 時間內(nèi)找到合適資源，并在 ? ?dOlog 時間內(nèi)修改該 資源結(jié)束時間。這樣做的 總時間復(fù)雜度也是 ? ?? ?ndnO log 。 第一個構(gòu)造算法證明了最少所用資源的數(shù)量，并用編程復(fù)雜度較低的方法構(gòu)造出了可行解。第二個貪心算法是基于第一個算法的結(jié)論得到的，編程復(fù)雜度也比第一種高，然而利用它的局部最優(yōu)性，還可以附加更多的條件。 例題 2： 2022年廣東省大學(xué)生程序競賽試題 Problem B 題目大意： 一個港口被分成了 ? ?101 ??mm 個區(qū)域，每個區(qū)域最多允許同 時?？?9 ? ?10000?rr 艘船，每艘船都只能停靠在特定的一個區(qū)域。有 ? ?1000001 ?? nn 艘船，已知每條船的到達(dá)時刻、離開時刻和它應(yīng)該進(jìn)入的區(qū)域。求一個調(diào)度方案使得能有最多的船得以?？?。 分析： 顯然每個區(qū)域都可以單獨(dú)處理?？梢园汛醋饕粋€區(qū)間，則該問題是問題 2的一個變化：規(guī)定使用資源的數(shù)量 r ，問最多能選出多少區(qū)間。在算法 2上稍加改動即可得出該題的算法。 算法： 將所有區(qū)間按右端點(diǎn)坐標(biāo)從小到大排序，順序處理每個 區(qū)間。對于每個區(qū)間，若能找到可用資源，則將該區(qū)間安排到一個可用的且右端點(diǎn)坐標(biāo)最大的資源；若找不到，則不去選它。 在前面的證明中我們已經(jīng)證明了選擇資源的局部最優(yōu)性，唯一剩余的問題是區(qū)間的取舍。如果該算法選擇了某區(qū)間 I ，而某最優(yōu)解中沒有選它，顯然最優(yōu)解選擇了一個與該區(qū)間重疊且右端點(diǎn)坐標(biāo)大于等于它的區(qū)間 I? ，我們用 I 替換 I? ,就構(gòu)成了一個包含 I 的最優(yōu)解；如果該算法沒有選擇某區(qū)間，顯然最優(yōu)解也不會選擇該區(qū)間。故該算法得出的解就是最優(yōu)解。 實(shí)現(xiàn)： 還是利用平衡二叉樹維護(hù)資源信息并尋找合適資源，處理每個區(qū)間的時間復(fù)雜度是 ? ?rOlog ， 故 總 時 間 復(fù) 雜 度 為 ： 排 序 ? ?nnO log + 處 理 區(qū) 間? ? ? ?rOnO log? = ? ?? ?nrnO log 。 有 n 個長度固定、但位置可變的區(qū)間，將它們?nèi)糠胖迷?),0[ ?? 上。每個區(qū) 10 間有兩個已知參數(shù)：長度 it 和最終期限 id ，設(shè) if 為其右端點(diǎn)坐標(biāo)。定義??? ????iiiiiii dfif dfifdfl 0 ， ? ?ini lL ??? 1max 。放置所有區(qū)間，使它們不互相重疊且最大延遲 L 最小。 算法： 將 所有區(qū)間按最終期限從小到大排序，順序安排各區(qū)間，使中間沒有空閑段。