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

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

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

一、思路

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

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

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

二、代碼

看下動畫就一目了然了：

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