數組的合并和升序排列_區間排程問題之區間合并

讀完本文，你可以去力扣拿下如下題目：

56.合并區間

-----------

上篇文章用貪心算法解決了區間排程問題：給你很多區間，讓你求其中的最大不重疊子集。

其實對于區間相關的問題，還有很多其他類型，本文就來講講區間合并問題（Merge Interval）。

LeetCode 第 56 題就是一道相關問題，題目很好了解：

我們解決區間問題的一般思路是先排序，然後觀察規律。

PS：

我認真寫了 100 多篇原創，手把手刷 200 道力扣題目，全部釋出在 labuladong的算法小抄，持續更新

。建議收藏，

按照我的文章順序刷題

，掌握各種算法套路後投再入題海就如魚得水了。

一、思路

一個區間可以表示為

[start, end]

，前文聊的區間排程問題，需要按

end

排序，以便滿足貪心選擇性質。而對于區間合并問題，其實按

end

和

start

排序都可以，不過為了清晰起見，我們選擇按

start

排序。

顯然，對于幾個相交區間合并後的結果區間

x

，

x.start

一定是這些相交區間中

start

最小的，

x.end

一定是這些相交區間中

end

最大的。

由于已經排了序，

x.start

很好确定，求

x.end

也很容易，可以類比在數組中找最大值的過程：

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 []
    # 按區間的 start 升序排列
    intervals.sort(key=lambda intv: intv[0])
    res = []
    res.append(intervals[0])

    for i in range(1, len(intervals)):
        curr = intervals[i]
        # res 中最後一個元素的引用
        last = res[-1]
        if curr[0] <= last[1]:
            # 找到最大的 end
            last[1] = max(last[1], curr[1])
        else:
            # 處理下一個待合并區間
            res.append(curr)
    return res
           

看下動畫就一目了然了：

至此，區間合并問題就解決了。本文篇幅短小，因為區間合并隻是區間問題的一個類型，後續還有一些區間問題。本想把所有問題類型都總結在一篇文章，但有讀者反應，長文隻會收藏不會看… 是以還是分成小短文吧，讀者有什麼看法可以在留言闆留言交流。

本文終，希望對你有幫助。

＿＿＿＿＿＿＿＿＿＿＿＿＿

我的 線上電子書 有 100 篇原創文章，手把手帶刷 200 道力扣題目，建議收藏！對應的 GitHub 算法倉庫 已經獲得了 70k star，歡迎标星！