56. 合并區(qū)間
題目來源：https://leetcode-cn.com/problems/merge-intervals
題目
給出一個(gè)區(qū)間的集合，請合并所有重疊的區(qū)間米酬。
示例 1:
輸入: [[1,3],[2,6],[8,10],[15,18]]
輸出: [[1,6],[8,10],[15,18]]
解釋: 區(qū)間 [1,3] 和 [2,6] 重疊, 將它們合并為 [1,6].
示例 2:
輸入: [[1,4],[4,5]]
輸出: [[1,5]]
解釋: 區(qū)間 [1,4] 和 [4,5] 可被視為重疊區(qū)間沛豌。
解題思路
思路：貪心算法
首先需要對題意進(jìn)行理解（以示例 1，示例 2 為例）：
示例 1：
示例 1
示例 2：
示例 2
上面示圖中赃额，線段比例并非準(zhǔn)確的比例加派，這里僅當(dāng)做輔助理解。
結(jié)合上面的圖以及示例輸出的結(jié)果可看出： 對區(qū)間進(jìn)行合并跳芳，那么兩個(gè)區(qū)間之間必然會有交集的部分芍锦。再看示例 2，這里交集的部分也可以是一個(gè)點(diǎn)飞盆。
同樣需要注意的地方是： 這里有個(gè)前提娄琉，就是需要區(qū)間要按照左端點(diǎn)進(jìn)行升序排序。
對給定的列表進(jìn)行排序后吓歇，同時(shí)添加結(jié)果集孽水，結(jié)合兩者進(jìn)行判斷是否有交集，從而決定是否要合并區(qū)間城看。
具體的算法：
- 對區(qū)間進(jìn)行排序女气，以區(qū)間左端點(diǎn)為準(zhǔn)進(jìn)行升序排序，然后進(jìn)行遍歷测柠；
- 如果遍歷的區(qū)間左端點(diǎn) > 結(jié)果集最后一個(gè)區(qū)間的右端點(diǎn)主卫，那么表示沒有交集，這里直接將區(qū)間添加到結(jié)果集即可鹃愤；
- 如果遍歷的區(qū)間左端點(diǎn) <= 結(jié)果集中最后一個(gè)區(qū)間的右端點(diǎn)完域，那么說明有交集凹耙，這里需要對區(qū)間進(jìn)行合并。具體的做法：對結(jié)果集中最后一個(gè)區(qū)間的右端點(diǎn)進(jìn)行更新（這里取兩個(gè)區(qū)間的大值）
對于上面產(chǎn)生交集的情況，將最后一個(gè)區(qū)間的右端點(diǎn)進(jìn)行更新為最大拌屏，達(dá)到合并更多區(qū)間的結(jié)果，這就是貪心策略端圈。
具體實(shí)現(xiàn)的代碼如下：
代碼實(shí)現(xiàn)
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
# 對數(shù)組進(jìn)行升序刚照，以數(shù)組元素區(qū)間左端為準(zhǔn)
intervals.sort(key=lambda x: x[0])
# 定義返回?cái)?shù)組
ret = []
# 這里合并的依據(jù)是區(qū)間一定是有交集的
# 即是一個(gè)區(qū)間左端點(diǎn) <= 另一個(gè)區(qū)間右端點(diǎn)
# 反之則沒有交集，則不需要合并
# 此時(shí)，一個(gè)區(qū)間的左端點(diǎn) > 另一個(gè)區(qū)間的右端點(diǎn)
# 這里主要比較的是排序后的數(shù)組區(qū)間與返回?cái)?shù)組的最后一個(gè)區(qū)間
for interval in intervals:
# 返回?cái)?shù)組為空時(shí)诉濒，先直接將第一個(gè)添加到數(shù)組
# 當(dāng)返回?cái)?shù)組不為空時(shí)专挪，則根據(jù)上面的依據(jù)進(jìn)行區(qū)分
# 先看返回?cái)?shù)組為空迫卢，或者區(qū)間沒有交集的情況
if not ret or interval[0] > ret[-1][1]:
ret.append(interval)
# 返回?cái)?shù)組不為空幻捏，有交集的情況，合并區(qū)間
# 更新返回?cái)?shù)組最后一個(gè)區(qū)間的右端點(diǎn)篡九，取兩區(qū)間的大值
else:
ret[-1][1] = max(ret[-1][1], interval[1])
return ret
實(shí)現(xiàn)結(jié)果
實(shí)現(xiàn)結(jié)果
以上就是使用貪心算法的思路谐岁，判斷區(qū)間是否可以合并，需要先對區(qū)間進(jìn)行排序榛臼，確定區(qū)間之間是否有交集伊佃，以此為依據(jù)更新結(jié)果集，進(jìn)而解決《56. 合并區(qū)間》問題的主要內(nèi)容沛善。
歡迎關(guān)注微信公眾號《書所集錄》
