讀完本文，你可以去力扣拿下如下題目：
-----------
本文是區(qū)間系列問題的第三篇，前兩篇分別講了區(qū)間的最大不相交子集和重疊區(qū)間的合并，今天再寫一個算法，可以快速找出兩組區(qū)間的交集。
先看下題目，LeetCode 第 986 題就是這個問題：
題目很好理解，就是讓你找交集，注意區(qū)間都是閉區(qū)間。
思路
解決區(qū)間問題的思路一般是先排序，以便操作，不過題目說已經(jīng)排好序了，那么可以用兩個索引指針在 A 和 B 中游走，把交集找出來，代碼大概是這樣的：
# A, B 形如 [[0,2],[5,10]...]
def intervalIntersection(A, B):
i, j = 0, 0
res = []
while i < len(A) and j < len(B):
# ...
j += 1
i += 1
return res
不難，我們先老老實實分析一下各種情況。
首先，對于兩個區(qū)間，我們用 [a1,a2] 和 [b1,b2] 表示在 A 和 B 中的兩個區(qū)間，那么什么情況下這兩個區(qū)間沒有交集呢：
只有這兩種情況，寫成代碼的條件判斷就是這樣：
if b2 < a1 or a2 < b1:
[a1,a2] 和 [b1,b2] 無交集
PS：我認(rèn)真寫了 100 多篇原創(chuàng)，手把手刷 200 道力扣題目，全部發(fā)布在 labuladong的算法小抄，持續(xù)更新。建議收藏，按照我的文章順序刷題，掌握各種算法套路后投再入題海就如魚得水了。
那么，什么情況下，兩個區(qū)間存在交集呢？根據(jù)命題的否定，上面邏輯的否命題就是存在交集的條件：
# 不等號取反，or 也要變成 and
if b2 >= a1 and a2 >= b1:
[a1,a2] 和 [b1,b2] 存在交集
接下來，兩個區(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)系：
while i < len(A) and j < len(B):
# ...
if b2 < a2:
j += 1
else:
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]
# 兩個區(qū)間存在交集
if b2 >= a1 and a2 >= b1:
# 計算出交集，加入 res
res.append([max(a1, b1), min(a2, b2)])
# 指針前進(jìn)
if b2 < a2: j += 1
else: i += 1
return res
總結(jié)一下，區(qū)間類問題看起來都比較復(fù)雜，情況很多難以處理，但實際上通過觀察各種不同情況之間的共性可以發(fā)現(xiàn)規(guī)律，用簡潔的代碼就能處理。
另外，區(qū)間問題沒啥特別厲害的奇技淫巧，其操作也樸實無華，但其應(yīng)用卻十分廣泛。
＿＿＿＿＿＿＿＿＿＿＿＿＿
我的 在線電子書 有 100 篇原創(chuàng)文章，手把手帶刷 200 道力扣題目，建議收藏！對應(yīng)的 GitHub 算法倉庫 已經(jīng)獲得了 70k star，歡迎標(biāo)星！
