我將演算法學習相關的資料已經整理到了Github ：https://github.com/youngyangyang04/leetcode-master，裡面還有leetcode刷題攻略、各個型別經典題目刷題順序、思維導圖看一看一定會有所收穫，如果給你有幫助給一個star支援一下吧！

56. 合併區間

題目連結：https://leetcode-cn.com/problems/merge-intervals/

給出一個區間的集合，請合併所有重疊的區間。

示例 1:輸入: intervals = [[1,3],[2,6],[8,10],[15,18]]輸出: [[1,6],[8,10],[15,18]]解釋: 區間 [1,3] 和 [2,6] 重疊, 將它們合併為 [1,6].

示例 2:輸入: intervals = [[1,4],[4,5]]輸出: [[1,5]]解釋: 區間 [1,4] 和 [4,5] 可被視為重疊區間。注意：輸入型別已於2019年4月15日更改。請重置預設程式碼定義以獲取新方法簽名。

提示：

intervals[i][0] <= intervals[i][1]思路

大家應該都感覺到了，此題一定要排序，那麼按照左邊界排序，還是右邊界排序呢？

都可以！

那麼我按照左邊界排序，排序之後區域性最優：每次合併都取最大的右邊界，這樣就可以合併更多的區間了，整體最優：合併所有重疊的區間。

區域性最優可以推出全域性最優，找不出反例，試試貪心。

那有同學問了，本來不就應該合併最大右邊界麼，這和貪心有啥關係？

有時候貪心就是常識！哈哈

按照左邊界從小到大排序之後，如果 intervals[i][0] < intervals[i - 1][1] 即intervals[i]左邊界 < intervals[i - 1]右邊界，則一定有重複，因為intervals[i]的左邊界一定是大於等於intervals[i - 1]的左邊界。

即：intervals[i]的左邊界在intervals[i - 1]左邊界和右邊界的範圍內，那麼一定有重複！

這麼說有點抽象，看圖：（「注意圖中區間都是按照左邊界排序之後了」）

56.合併區間

知道如何判斷重複之後，剩下的就是合併了，如何去模擬合併區間呢？

其實就是用合併區間後左邊界和右邊界，作為一個新的區間，加入到result數組裡就可以了。如果沒有合併就把原區間加入到result陣列。

C++程式碼如下：

class Solution {public:    // 按照區間左邊界從小到大排序    static bool cmp (const vector<int>& a, const vector<int>& b) {        return a[0] < b[0];    }    vector<vector<int>> merge(vector<vector<int>>& intervals) {        vector<vector<int>> result;        if (intervals.size() == 0) return result;        sort(intervals.begin(), intervals.end(), cmp);        bool flag = false; // 標記最後一個區間有沒有合併        int length = intervals.size();        for (int i = 1; i < length; i++) {            int start = intervals[i - 1][0];    // 初始為i-1區間的左邊界            int end = intervals[i - 1][1];      // 初始i-1區間的右邊界            while (i < length && intervals[i][0] <= end) { // 合併區間                end = max(end, intervals[i][1]);    // 不斷更新右區間                if (i == length - 1) flag = true;   // 最後一個區間也合併了                i++;                                // 繼續合併下一個區間            }            // start和end是表示intervals[i - 1]的左邊界右邊界，所以最優intervals[i]區間是否合併了要標記一下            result.push_back({start, end});         }        // 如果最後一個區間沒有合併，將其加入result        if (flag == false) {            result.push_back({intervals[length - 1][0], intervals[length - 1][1]});        }        return result;    }};

當然以上程式碼有冗餘一些，可以最佳化一下，如下：（思路是一樣的）

class Solution {public:    vector<vector<int>> merge(vector<vector<int>>& intervals) {        vector<vector<int>> result;        if (intervals.size() == 0) return result;        // 排序的引數使用了lamda表示式        sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b){return a[0] < b[0];});        result.push_back(intervals[0]);        for (int i = 1; i < intervals.size(); i++) {            if (result.back()[1] >= intervals[i][0]) { // 合併區間                result.back()[1] = max(result.back()[1], intervals[i][1]);            } else {                result.push_back(intervals[i]);            }        }        return result;    }};

時間複雜度：O(nlogn) ，有一個快排空間複雜度：O(1)，不算result陣列（返回值所需容器佔的空間）總結

對於貪心演算法，很多同學都是：「如果能憑常識直接做出來，就會感覺不到自己用了貪心, 一旦第一直覺想不出來, 可能就一直想不出來了」。

那應該怎麼辦呢？

打算從頭開始打卡的錄友，可以在「演算法彙總」這裡找到歷史文章，很多錄友都在從頭打卡，你並不孤單！

-------end-------

我是程式設計師Carl，個人主頁：https://github.com/youngyangyang04

這裡每天8:35準時推送一道經典演算法題目，我選擇的每道題目都不是孤立的，而是由淺入深，環環相扣，幫你梳理演算法知識脈絡，輕鬆學演算法！