讀完本文，你不僅學(xué)會(huì)了算法套路，還可以順便去 LeetCode 上拿下如下題目：
-----------
經(jīng)常有讀者問區(qū)間相關(guān)的問題，今天寫一篇文章，秒殺三道區(qū)間相關(guān)的問題。
所謂區(qū)間問題，就是線段問題，讓你合并所有線段、找出線段的交集等等。主要有兩個(gè)技巧：
1、排序。常見的排序方法就是按照區(qū)間起點(diǎn)排序，或者先按照起點(diǎn)升序排序，若起點(diǎn)相同，則按照終點(diǎn)降序排序。當(dāng)然，如果你非要按照終點(diǎn)排序，無非對稱操作，本質(zhì)都是一樣的。
2、畫圖。就是說不要偷懶，勤動(dòng)手，兩個(gè)區(qū)間的相對位置到底有幾種可能，不同的相對位置我們的代碼應(yīng)該怎么去處理。
廢話不多說，下面我們來做題。
區(qū)間覆蓋問題
這是力扣第 1288 題，看下題目：
題目問我們，去除被覆蓋區(qū)間之后，還剩下多少區(qū)間，那么我們可以先算一算，被覆蓋區(qū)間有多少個(gè)，然后和總數(shù)相減就是剩余區(qū)間數(shù)。
對于這種區(qū)間問題，如果沒啥頭緒，首先排個(gè)序看看，比如我們按照區(qū)間的起點(diǎn)進(jìn)行升序排序：
排序之后，兩個(gè)相鄰區(qū)間可能有如下三種相對位置：
PS：我認(rèn)真寫了 100 多篇原創(chuàng)，手把手刷 200 道力扣題目，全部發(fā)布在 labuladong的算法小抄，持續(xù)更新。建議收藏，按照我的文章順序刷題，掌握各種算法套路后投再入題海就如魚得水了。
對于這三種情況，我們應(yīng)該這樣處理：
對于情況一，找到了覆蓋區(qū)間。
對于情況二，兩個(gè)區(qū)間可以合并，成一個(gè)大區(qū)間。
對于情況三，兩個(gè)區(qū)間完全不相交。
依據(jù)幾種情況，我們可以寫出如下代碼：
int removeCoveredIntervals(int[][] intvs) {
// 按照起點(diǎn)升序排列，起點(diǎn)相同時(shí)降序排列
Arrays.sort(intvs, (a, b) -> {
if (a[0] == b[0]) {
return b[1] - a[1];
}
return a[0] - b[0];
});
// 記錄合并區(qū)間的起點(diǎn)和終點(diǎn)
int left = intvs[0][0];
int right = intvs[0][1];
int res = 0;
for (int i = 1; i < intvs.length; i++) {
int[] intv = intvs[i];
// 情況一，找到覆蓋區(qū)間
if (left <= intv[0] && right >= intv[1]) {
res++;
}
// 情況二，找到相交區(qū)間，合并
if (right >= intv[0] && right <= intv[1]) {
right = intv[1];
}
// 情況三，完全不相交，更新起點(diǎn)和終點(diǎn)
if (right < intv[0]) {
left = intv[0];
right = intv[1];
}
}
return intvs.length - res;
}
以上就是本題的解法代碼，起點(diǎn)升序排列，終點(diǎn)降序排列的目的是防止如下情況：
對于這兩個(gè)起點(diǎn)相同的區(qū)間，我們需要保證長的那個(gè)區(qū)間在上面（按照終點(diǎn)降序），這樣才會(huì)被判定為覆蓋，否則會(huì)被錯(cuò)誤地判定為相交，少算一個(gè)覆蓋區(qū)間。
區(qū)間合并問題
力扣第 56 題就是一道相關(guān)問題，題目很好理解：
我們解決區(qū)間問題的一般思路是先排序，然后觀察規(guī)律。
一個(gè)區(qū)間可以表示為 [start, end]，前文聊的區(qū)間調(diào)度問題，需要按 end 排序，以便滿足貪心選擇性質(zhì)。而對于區(qū)間合并問題，其實(shí)按 end 和 start 排序都可以，不過為了清晰起見，我們選擇按 start 排序。
顯然，對于幾個(gè)相交區(qū)間合并后的結(jié)果區(qū)間 x，x.start 一定是這些相交區(qū)間中 start 最小的，x.end 一定是這些相交區(qū)間中 end 最大的。
由于已經(jīng)排了序，x.start 很好確定，求 x.end 也很容易，可以類比在數(shù)組中找最大值的過程：
int max_ele = arr[0];
for (int i = 1; i < arr.length; i++)
max_ele = max(max_ele, arr[i]);
return max_ele;
然后就可以寫出完整代碼
# intervals 形如 [[1,3],[2,6]...]
def merge(intervals):
if not intervals: return []
# 按區(qū)間的 start 升序排列
intervals.sort(key=lambda intv: intv[0])
res = []
res.append(intervals[0])
for i in range(1, len(intervals)):
curr = intervals[i]
# res 中最后一個(gè)元素的引用
last = res[-1]
if curr[0] <= last[1]:
# 找到最大的 end
last[1] = max(last[1], curr[1])
else:
# 處理下一個(gè)待合并區(qū)間
res.append(curr)
return res
區(qū)間交集問題
先看下題目，力扣第 986 題就是這個(gè)問題：
題目很好理解，就是讓你找交集，注意區(qū)間都是閉區(qū)間。
PS：我認(rèn)真寫了 100 多篇原創(chuàng)，手把手刷 200 道力扣題目，全部發(fā)布在 labuladong的算法小抄，持續(xù)更新。建議收藏，按照我的文章順序刷題，掌握各種算法套路后投再入題海就如魚得水了。
解決區(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í)分析一下各種情況。
首先，對于兩個(gè)區(qū)間，我們用 [a1,a2] 和 [b1,b2] 表示在 A 和 B 中的兩個(gè)區(qū)間，那么什么情況下這兩個(gè)區(qū)間沒有交集呢：
只有這兩種情況，寫成代碼的條件判斷就是這樣：
if b2 < a1 or a2 < b1:
[a1,a2] 和 [b1,b2] 無交集
那么，什么情況下，兩個(gè)區(qū)間存在交集呢？根據(jù)命題的否定，上面邏輯的否命題就是存在交集的條件：
# 不等號取反，or 也要變成 and
if b2 >= a1 and a2 >= b1:
[a1,a2] 和 [b1,b2] 存在交集
接下來，兩個(gè)區(qū)間存在交集的情況有哪些呢？窮舉出來：
這很簡單吧，就這四種情況而已。那么接下來思考，這幾種情況下，交集是否有什么共同點(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ī)律，用簡潔的代碼就能處理。
相關(guān)推薦：
＿＿＿＿＿＿＿＿＿＿＿＿＿
我的 在線電子書 有 100 篇原創(chuàng)文章，手把手帶刷 200 道力扣題目，建議收藏！對應(yīng)的 GitHub 算法倉庫 已經(jīng)獲得了 70k star，歡迎標(biāo)星！
