用算法優(yōu)雅地求出兩組區(qū)間的交集

本文是區(qū)間系列問題的第三篇，前兩篇分別講了區(qū)間的最大不相交子集和重疊區(qū)間的合并，今天再寫一個算法，可以快速找出兩組區(qū)間的交集。

先看下題目，LeetCode 第 986 題就是這個問題：

題目很好理解，就是讓你找交集，注意區(qū)間都是閉區(qū)間。

思路

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

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

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

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

if b2 < a1 or a2 < b1:
    [a1,a2] 和 [b1,b2] 無交集

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

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

這很簡單吧，就這四種情況而已。那么接下來思考，這幾種情況下，交集是否有什么共同點呢？

我們驚奇地發(fā)現(xiàn)，交集區(qū)間是有規(guī)律的！如果交集區(qū)間是[c1,c2]，那么c1=max(a1,b1)，c2=min(a2,b2)！這一點就是尋找交集的核心，我們把代碼更進(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)（遞增）的，什么時候應(yīng)該前進(jìn)呢？

結(jié)合動畫示例就很好理解了，是否前進(jìn)，只取決于a2和b2的大小關(guān)系：

代碼

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