本文是區(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)！這一點就是尋找交集的核心,，我們把代碼更進一步：

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肯定要前進（遞增）的，什么時候應該前進呢,？

結合動畫示例就很好理解了,，是否前進，只取決于a2和b2的大小關系：

代碼

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