讀完本文，你可以去力扣拿下如下題目：
-----------
本文是區(qū)間系列問題的第三篇，前兩篇分別講了區(qū)間的最大不相交子集和重疊區(qū)間的合并夜矗，今天再寫一個(gè)算法裤园，可以快速找出兩組區(qū)間的交集询筏。
先看下題目破花，LeetCode 第 986 題就是這個(gè)問題：
題目很好理解滋尉，就是讓你找交集玉控，注意區(qū)間都是閉區(qū)間。
思路
解決區(qū)間問題的思路一般是先排序狮惜，以便操作高诺，不過題目說已經(jīng)排好序了，那么可以用兩個(gè)索引指針在 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
不難，我們先老老實(shí)實(shí)分析一下各種情況开泽。
首先牡拇，對(duì)于兩個(gè)區(qū)間，我們用 [a1,a2] 和 [b1,b2] 表示在 A 和 B 中的兩個(gè)區(qū)間穆律，那么什么情況下這兩個(gè)區(qū)間沒有交集呢：
只有這兩種情況惠呼，寫成代碼的條件判斷就是這樣：
if b2 < a1 or a2 < b1:
[a1,a2] 和 [b1,b2] 無交集
PS：我認(rèn)真寫了 100 多篇原創(chuàng)，手把手刷 200 道力扣題目峦耘，全部發(fā)布在 labuladong的算法小抄剔蹋，持續(xù)更新。建議收藏辅髓，按照我的文章順序刷題泣崩，掌握各種算法套路后投再入題海就如魚得水了。
那么利朵，什么情況下，兩個(gè)區(qū)間存在交集呢猎莲？根據(jù)命題的否定绍弟，上面邏輯的否命題就是存在交集的條件：
# 不等號(hào)取反，or 也要變成 and
if b2 >= a1 and a2 >= b1:
[a1,a2] 和 [b1,b2] 存在交集
接下來著洼，兩個(gè)區(qū)間存在交集的情況有哪些呢樟遣？窮舉出來：
這很簡(jiǎn)單吧而叼，就這四種情況而已。那么接下來思考豹悬，這幾種情況下葵陵，交集是否有什么共同點(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)呢？
結(jié)合動(dòng)畫示例就很好理解了笔喉，是否前進(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]
# 兩個(gè)區(qū)間存在交集
if b2 >= a1 and a2 >= b1:
# 計(jì)算出交集，加入 res
res.append([max(a1, b1), min(a2, b2)])
# 指針前進(jìn)
if b2 < a2: j += 1
else: i += 1
return res
總結(jié)一下常挚，區(qū)間類問題看起來都比較復(fù)雜作谭，情況很多難以處理，但實(shí)際上通過觀察各種不同情況之間的共性可以發(fā)現(xiàn)規(guī)律待侵，用簡(jiǎn)潔的代碼就能處理丢早。
另外，區(qū)間問題沒啥特別厲害的奇技淫巧秧倾，其操作也樸實(shí)無華怨酝，但其應(yīng)用卻十分廣泛。
＿＿＿＿＿＿＿＿＿＿＿＿＿
我的 在線電子書 有 100 篇原創(chuàng)文章那先，手把手帶刷 200 道力扣題目农猬，建議收藏！對(duì)應(yīng)的 GitHub 算法倉庫 已經(jīng)獲得了 70k star售淡，歡迎標(biāo)星斤葱！
