今天是LeetCode專題的第33篇文章，我們一起來看LeetCode的第56題，它的難度是Medium。

題意

這道題的題意也很簡單，只有一句話：「Given a collection of intervals, merge all overlapping intervals.」

interval是間隔、區間的意思，也就是說題目會給我們一系列區間，讓我們把這些區間合併在一起。

我們看下題目給的樣例來感受一下：

「

Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

「

Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

分析

通過觀察樣例，我們發現題目通過數組給定區間，每個區間有兩個端點。兩個區間能夠合併的條件，就是互相之間有交叉的部分。我們看下下圖，這應該很直觀。

當兩個區間[s1, e1]和[s2, e2]中的e1 >= s2時，這兩個區間就可以進行合併。合併之後得到的新區間是[s1, e2]。

但是這存在一個小問題，我們如何能判斷第一個區間一定在第二個區間的左側呢，會不會發生重疊呢？

如果是這種情況那麼合併之後的結果就是[s2, e2]了，另外一個問題是，這樣的區間一共有N個，我們怎麼判斷合併的順序呢？很有可能出現AB兩個區間原本不能合併，但是A合併了區間C之後又可以和B合併的情況。如果我們枚舉的話會很麻煩，我們不但需要考慮合併的時候會發生的種種情況，還需要考慮合併的發生順序。而且我們也很難得知是否所有能夠合併的區間已經合併完成。

題解

我們梳理一下目前遇到的問題，第一個問題是區間根據位置的不同合併之後的結果可能有多個。第二個問題是區間合併之後會創建新的合併的可能，第三個問題是我們判斷當前是否還有合併的可能開銷很大。

其中第三個問題是前兩個問題導致的，只要解決了其中一個，第三個問題自然迎刃而解。其中第二個問題是無法解決的，因為這是區間合併的天然屬性，我們執行區間合併必然會有這樣的情況發生。所以我們只能針對第一個問題下手，合併之後的結果可能有多種的本質原因是區間的位置關係可能有多個。A和B合併，A可以出現在B的左側，也可以出現在B的右側。再根據區間長短關係，所以才導致了多種結果。

如果我們能夠保證A一定出現在B的左側，那麼A和B就只有三種情況。一種是A和B不相交，也就是不能合併。第二種是A和B相交，第三種是A包含B。

我們把圖畫出來，很容易發現後面兩種能夠合併的情況其實可以概括成一種，它們合併之後的結果都是[s1, max(e1, e2)]。

既然如此，本題的關鍵就是區間之間的順序。假如我們保證了區間的順序，我們依次合併顯然可以很容易得到結果。但是我們怎麼得到區間順序呢？

其實很簡單，就是排序，既然區間本來沒有順序，我們對它們排序，不就有順序了嗎？

我們可以規定左側端點小的區間排在前面，如果兩個區間左端點一致，右端點小的靠前。這是什麼？這其實就是字典序排序，在Python當中我們可以直接調用sorted對多元素的list進行字典序排序。如果是其他語言，也不麻煩，我們可以自己定義比較算子，一樣可以解決。

既然區間有序了，我們只需要從左到右遍歷就可以覆蓋所有情況了，第三個問題也就解決了。

最後，我們來看下代碼，只要想到了排序，這道題並不難。但是初學者往往很難想到排序上，這當中的思維推導過程才是我們需要熟悉的。

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        ret = []
        if len(intervals) == 0:
            return ret
        # 字典序排序
        intervals = sorted(intervals)
        # l，r表示當前區間的兩個端點
        l, r = intervals[0]
        # 從1開始遍歷區間，進行合併
        for i in range(1, len(intervals)):
            s, e = intervals[i]
            # 如果可以合併，維護合併之後的右端點
            if s <= r:
                r = max(r, e)
            else:
            # 否則加入答案，將i區間作為當前進行合併的區間
                ret.append([l, r])
                l, r = s, e
    ret.append([l, r])
    <span class="hljs-keyword" style="color: #333; font-weight: bold; line-height: 26px;">return</span> ret