區間問題之合并相交區間

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

其實對于區間相關的問題，還有很多其他類型，本文就來講講區間合并問題（Merge Interval）。LeetCode 第 56 題就是一道相關問題，題目很好理解：

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

一、思路

一個區間可以表示為[start,end]，前文聊的區間調度問題，需要按end排序，以便滿足貪心選擇性質。而對于區間合并問題，其實按end和start排序都可以，不過為了清晰起見，我們選擇按start排序。

顯然，對于幾個相交區間合并后的結果區間x，x.start一定是這些相交區間中start最小的，x.end一定是這些相交區間中end最大的。

由于已經排了序，x.start很好確定，求x.end也很容易，可以類比在數組中找最大值的過程：

二、代碼

看下動畫就一目了然了：

至此，區間合并問題就解決了。本文篇幅短小，因為區間合并只是區間問題的一個類型，后續還有一些區間問題。本想把所有問題類型都總結在一篇文章，但有讀者反應，長文只會收藏不會看… 所以還是分成小短文吧，歡迎留言寫下你的看法。