之前面試，被問(wèn)到一道非常經(jīng)典且非常實(shí)用的算法題目：會(huì)議室安排問(wèn)題。

力扣上類似的問(wèn)題是會(huì)員題目，你可能沒(méi)辦法做，但對(duì)于這種經(jīng)典的算法題，掌握思路還是必要的。

先說(shuō)下題目，給你輸入若干形如[begin, end]的區(qū)間，代表若干會(huì)議的開(kāi)始時(shí)間和結(jié)束時(shí)間，請(qǐng)你計(jì)算至少需要申請(qǐng)多少間會(huì)議室。

函數(shù)簽名如下：

//返回需要申請(qǐng)的會(huì)議室數(shù)量
intminMeetingRooms(int[][]meetings);

比如給你輸入meetings = [[0,30],[5,10],[15,20]]，算法應(yīng)該返回 2，因?yàn)楹髢蓚€(gè)會(huì)議和第一個(gè)會(huì)議時(shí)間是沖突的，至少申請(qǐng)兩個(gè)會(huì)議室才能讓所有會(huì)議順利進(jìn)行。

如果會(huì)議之間的時(shí)間有重疊，那就得額外申請(qǐng)會(huì)議室來(lái)開(kāi)會(huì)，想求至少需要多少間會(huì)議室，就是讓你計(jì)算同一時(shí)刻最多有多少會(huì)議在同時(shí)進(jìn)行。

換句話說(shuō)，如果把每個(gè)會(huì)議的起止時(shí)間看做一個(gè)線段區(qū)間，那么題目就是讓你求最多有幾個(gè)重疊區(qū)間，僅此而已。

對(duì)于這種時(shí)間安排的問(wèn)題，本質(zhì)上講就是區(qū)間調(diào)度問(wèn)題，十有八九得排序，然后找規(guī)律來(lái)解決。

題目延伸

我們之前寫(xiě)過(guò)很多區(qū)間調(diào)度相關(guān)的文章，這里就順便幫大家梳理一下這類問(wèn)題的思路：

第一個(gè)場(chǎng)景，假設(shè)現(xiàn)在只有一個(gè)會(huì)議室，還有若干會(huì)議，你如何將盡可能多的會(huì)議安排到這個(gè)會(huì)議室里？

這個(gè)問(wèn)題需要將這些會(huì)議（區(qū)間）按結(jié)束時(shí)間（右端點(diǎn)）排序，然后進(jìn)行處理，詳見(jiàn)前文貪心算法做時(shí)間管理。

第二個(gè)場(chǎng)景，給你若干較短的視頻片段，和一個(gè)較長(zhǎng)的視頻片段，請(qǐng)你從較短的片段中盡可能少地挑出一些片段，拼接出較長(zhǎng)的這個(gè)片段。

這個(gè)問(wèn)題需要將這些視頻片段（區(qū)間）按開(kāi)始時(shí)間（左端點(diǎn)）排序，然后進(jìn)行處理，詳見(jiàn)前文剪視頻剪出一個(gè)貪心算法。

第三個(gè)場(chǎng)景，給你若干區(qū)間，其中可能有些區(qū)間比較短，被其他區(qū)間完全覆蓋住了，請(qǐng)你刪除這些被覆蓋的區(qū)間。

這個(gè)問(wèn)題需要將這些區(qū)間按左端點(diǎn)排序，然后就能找到并刪除那些被完全覆蓋的區(qū)間了，詳見(jiàn)前文刪除覆蓋區(qū)間。

第四個(gè)場(chǎng)景，給你若干區(qū)間，請(qǐng)你將所有有重疊部分的區(qū)間進(jìn)行合并。

這個(gè)問(wèn)題需要將這些區(qū)間按左端點(diǎn)排序，方便找出存在重疊的區(qū)間，詳見(jiàn)前文合并重疊區(qū)間。

第五個(gè)場(chǎng)景，有兩個(gè)部門(mén)同時(shí)預(yù)約了同一個(gè)會(huì)議室的若干時(shí)間段，請(qǐng)你計(jì)算會(huì)議室的沖突時(shí)段。

這個(gè)問(wèn)題就是給你兩組區(qū)間列表，請(qǐng)你找出這兩組區(qū)間的交集，這需要你將這些區(qū)間按左端點(diǎn)排序，詳見(jiàn)前文區(qū)間交集問(wèn)題。

第六個(gè)場(chǎng)景，假設(shè)現(xiàn)在只有一個(gè)會(huì)議室，還有若干會(huì)議，如何安排會(huì)議才能使這個(gè)會(huì)議室的閑置時(shí)間最少？

這個(gè)問(wèn)題需要?jiǎng)觿?dòng)腦筋，說(shuō)白了這就是個(gè) 0-1 背包問(wèn)題的變形：

會(huì)議室可以看做一個(gè)背包，每個(gè)會(huì)議可以看做一個(gè)物品，物品的價(jià)值就是會(huì)議的時(shí)長(zhǎng)，請(qǐng)問(wèn)你如何選擇物品（會(huì)議）才能最大化背包中的價(jià)值（會(huì)議室的使用時(shí)長(zhǎng)）？

當(dāng)然，這里背包的約束不是一個(gè)最大重量，而是各個(gè)物品（會(huì)議）不能互相沖突。把各個(gè)會(huì)議按照結(jié)束時(shí)間進(jìn)行排序，然后參考前文0-1 背包問(wèn)題詳解的思路即可解決，等我以后有機(jī)會(huì)可以寫(xiě)一寫(xiě)這個(gè)問(wèn)題。

第七個(gè)場(chǎng)景，就是本文想講的場(chǎng)景，給你若干會(huì)議，讓你合理申請(qǐng)會(huì)議室。

好了，舉例了這么多，來(lái)看看今天的這個(gè)問(wèn)題如何解決。

題目分析

重復(fù)一下題目的本質(zhì)：

給你輸入若干時(shí)間區(qū)間，讓你計(jì)算同一時(shí)刻「最多」有幾個(gè)區(qū)間重疊。

題目的關(guān)鍵點(diǎn)在于，給你任意一個(gè)時(shí)刻，你是否能夠說(shuō)出這個(gè)時(shí)刻有幾個(gè)會(huì)議在同時(shí)進(jìn)行？

如果可以做到，那我遍歷所有的時(shí)刻，找個(gè)最大值，就是需要申請(qǐng)的會(huì)議室數(shù)量。

有沒(méi)有一種數(shù)據(jù)結(jié)構(gòu)或者算法，給我輸入若干區(qū)間，我能知道每個(gè)位置有多少個(gè)區(qū)間重疊？

老讀者肯定可以聯(lián)想到之前說(shuō)過(guò)的一個(gè)算法技巧：差分?jǐn)?shù)組技巧。

把時(shí)間線想象成一個(gè)初始值為 0 的數(shù)組，每個(gè)時(shí)間區(qū)間[i, j]就相當(dāng)于一個(gè)子數(shù)組，這個(gè)時(shí)間區(qū)間有一個(gè)會(huì)議，那我就把這個(gè)子數(shù)組中的元素都加一。

最后，每個(gè)時(shí)刻有幾個(gè)會(huì)議我不就知道了嗎？我遍歷整個(gè)數(shù)組，不就知道至少需要幾間會(huì)議室了嗎？

舉例來(lái)說(shuō)，如果輸入meetings = [[0,30],[5,10],[15,20]]，那么我們就給數(shù)組中[0,30],[5,10],[15,20]這幾個(gè)索引區(qū)間分別加一，最后遍歷數(shù)組，求個(gè)最大值就行了。

還記得嗎，差分?jǐn)?shù)組技巧可以在 O(1) 時(shí)間對(duì)整個(gè)區(qū)間的元素進(jìn)行加減，所以可以拿來(lái)解決這道題。

不過(guò)，這個(gè)解法的效率不算高，所以我這里不準(zhǔn)備具體寫(xiě)差分?jǐn)?shù)組的解法，參照差分?jǐn)?shù)組技巧的原理，有興趣的讀者可以自己嘗試去實(shí)現(xiàn)。

基于差分?jǐn)?shù)組的思路，我們可以推導(dǎo)出一種更高效，更優(yōu)雅的解法。

我們首先把這些會(huì)議的時(shí)間區(qū)間進(jìn)行投影：

紅色的點(diǎn)代表每個(gè)會(huì)議的開(kāi)始時(shí)間點(diǎn)，綠色的點(diǎn)代表每個(gè)會(huì)議的結(jié)束時(shí)間點(diǎn)。

現(xiàn)在假想有一條帶著計(jì)數(shù)器的線，在時(shí)間線上從左至右進(jìn)行掃描，每遇到紅色的點(diǎn)，計(jì)數(shù)器count加一，每遇到綠色的點(diǎn)，計(jì)數(shù)器count減一：

這樣一來(lái)，每個(gè)時(shí)刻有多少個(gè)會(huì)議在同時(shí)進(jìn)行，就是計(jì)數(shù)器count的值，count的最大值，就是需要申請(qǐng)的會(huì)議室數(shù)量。

對(duì)差分?jǐn)?shù)組技巧熟悉的讀者一眼就能看出來(lái)了，這個(gè)掃描線其實(shí)就是差分?jǐn)?shù)組的遍歷過(guò)程，所以我們說(shuō)這是差分?jǐn)?shù)組技巧衍生出來(lái)的解法。

代碼實(shí)現(xiàn)

那么，如何寫(xiě)代碼實(shí)現(xiàn)這個(gè)掃描的過(guò)程呢？

首先，對(duì)區(qū)間進(jìn)行投影，就相當(dāng)于對(duì)每個(gè)區(qū)間的起點(diǎn)和終點(diǎn)分別進(jìn)行排序：

intminMeetingRooms(int[][]meetings){
intn=meetings.length;
int[]begin=newint[n];
int[]end=newint[n];
//把左端點(diǎn)和右端點(diǎn)單獨(dú)拿出來(lái)
for(inti=0;i0];
end[i]=meetings[i][1];
}
//排序后就是圖中的紅點(diǎn)
Arrays.sort(begin);
//排序后就是圖中的綠點(diǎn)
Arrays.sort(end);

//...
}

然后就簡(jiǎn)單了，掃描線從左向右前進(jìn)，遇到紅點(diǎn)就對(duì)計(jì)數(shù)器加一，遇到綠點(diǎn)就對(duì)計(jì)數(shù)器減一，計(jì)數(shù)器count的最大值就是答案：

intminMeetingRooms(int[][]meetings){
intn=meetings.length;
int[]begin=newint[n];
int[]end=newint[n];
for(inti=0;i0];
end[i]=meetings[i][1];
}
Arrays.sort(begin);
Arrays.sort(end);

//掃描過(guò)程中的計(jì)數(shù)器
intcount=0;
//雙指針技巧
intres=0,i=0,j=0;
while(iif(begin[i]//掃描到一個(gè)紅點(diǎn)
count++;
i++;
}else{
//掃描到一個(gè)綠點(diǎn)
count--;
j++;
}
//記錄掃描過(guò)程中的最大值
res=Math.max(res,count);
}

returnres;
}

這里使用的是雙指針技巧，你可以認(rèn)為指針i就是那根掃描線，根據(jù)i, j的相對(duì)位置就可以模擬掃描線前進(jìn)的過(guò)程。

至此，這道題就做完了。當(dāng)然，這個(gè)題目也可以變形，比如給你若干會(huì)議，問(wèn)你k個(gè)會(huì)議室夠不夠用，其實(shí)你套用本文的解法代碼，也可以很輕松解決。