區(qū)間調(diào)度之區(qū)間交集問(wèn)題

區(qū)間調(diào)度問(wèn)題共寫(xiě)了3片博客，前兩篇重疊區(qū)間和區(qū)間合并分別講了區(qū)間的最大不相交子集和重疊區(qū)間的合并，今天再寫(xiě)一個(gè)算法，可以快速找出兩組區(qū)間的交集。

一、解題思路

解決區(qū)間問(wèn)題的思路一般是先排序，以便操作，不過(guò)題目說(shuō)已經(jīng)排好序了，那么可以用兩個(gè)索引指針在 A 和 B 中游走，把交集找出來(lái)，代碼大概是這樣的：

# A, B 形如 [[0,2],[5,10]...] def intervalIntersection(A, B):i, j = 0, 0res = []while i < len(A) and j < len(B):# ...j += 1i += 1return res

不難，我們先老老實(shí)實(shí)分析一下各種情況。

首先，對(duì)于兩個(gè)區(qū)間，我們用 [a1,a2] 和 [b1,b2] 表示在 A 和 B 中的兩個(gè)區(qū)間，那么什么情況下這兩個(gè)區(qū)間沒(méi)有交集呢：

只有這兩種情況，寫(xiě)成代碼的條件判斷就是這樣：

if b2 < a1 or a2 < b1:[a1,a2] 和 [b1,b2] 無(wú)交集

那么，什么情況下，兩個(gè)區(qū)間存在交集呢？根據(jù)命題的否定，上面邏輯的否命題就是存在交集的條件：

# 不等號(hào)取反，or 也要變成 and if b2 >= a1 and a2 >= b1:[a1,a2] 和 [b1,b2] 存在交集

接下來(lái)，兩個(gè)區(qū)間存在交集的情況有哪些呢？窮舉出來(lái)：

這很簡(jiǎn)單吧，就這四種情況而已。那么接下來(lái)思考，這幾種情況下，交集是否有什么共同點(diǎn)呢？

我們驚奇地發(fā)現(xiàn)，交集區(qū)間是有規(guī)律的！如果交集區(qū)間是 [c1,c2]，那么 c1=max(a1,b1)，c2=min(a2,b2)！這一點(diǎn)就是尋找交集的核心，我們把代碼更進(jìn)一步：

while i < len(A) and j < len(B):a1, a2 = A[i][0], A[i][1]b1, b2 = B[j][0], B[j][1]if b2 >= a1 and a2 >= b1:res.append([max(a1, b1), min(a2, b2)])# ...

最后一步，我們的指針 i 和 j 肯定要前進(jìn)（遞增）的，什么時(shí)候應(yīng)該前進(jìn)呢？

是否前進(jìn)，只取決于 a2 和 b2 的大小關(guān)系。代碼：

while i < len(A) and j < len(B):# ...if b2 < a2:j += 1else:i += 1

完整代碼：

# A, B 形如 [[0,2],[5,10]...] def intervalIntersection(A, B):i, j = 0, 0 # 雙指針res = []while i < len(A) and j < len(B):a1, a2 = A[i][0], A[i][1]b1, b2 = B[j][0], B[j][1]# 兩個(gè)區(qū)間存在交集if b2 >= a1 and a2 >= b1:# 計(jì)算出交集，加入 resres.append([max(a1, b1), min(a2, b2)])# 指針前進(jìn)if b2 < a2: j += 1else: i += 1return res

C++代碼：

class Solution { public:vector<vector<int>> intervalIntersection(vector<vector<int>>& A, vector<vector<int>>& B) {//保存結(jié)果vector<vector<int>> ret;if(A.empty() || B.empty()){return ret;}//i和j兩個(gè)下標(biāo)索引int i = 0;int j = 0;while(i < A.size() && j < B.size()){//下面四個(gè)變量的含義相見(jiàn)博客int a1 = A[i][0];int a2 = A[i][1];int b1 = B[j][0];int b2 = B[j][1];//代表區(qū)間有交集，自己畫(huà)個(gè)圖就OKif(b2 >= a1 && a2 >= b1){//max(a1,b1),min(a2,b2)兩個(gè)區(qū)間的交集部分ret.push_back({max(a1,b1),min(a2,b2)});}//更新i和j下標(biāo)索引，b2 < a2 就代表i所在的區(qū)間大于j所在的區(qū)間，更新j//是因?yàn)閕區(qū)間長(zhǎng)于j區(qū)間的部分還可能和j的下一個(gè)區(qū)間繼續(xù)重疊，還需要繼續(xù)判斷//所以更新j而不是更新iif(b2 < a2){j++;}else//反之同理{i++;}} return ret;} };

總結(jié)一下，區(qū)間類(lèi)問(wèn)題看起來(lái)都比較復(fù)雜，情況很多難以處理，但實(shí)際上通過(guò)觀(guān)察各種不同情況之間的共性可以發(fā)現(xiàn)規(guī)律，用簡(jiǎn)潔的代碼就能處理。

總結(jié)

以上是生活随笔為你收集整理的区间调度之区间交集问题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。