前言

連假結束加班加起來QQ 今天就來點輕鬆點，一樣是top 100 liked的題目56. Merge Intervals，雖然是medium，但這題應用的概念昨天Day 16已經提過，就當作是複習，順手把它解掉吧！

想法

前一天有提到過其實我是先寫過這題，掌握到這個套路之後把昨天的題目解掉，這題算是經典的基礎，很多類似的題目都可以沿用此概念再去延伸或變形。題目的要求是要把interval跟interval之間有overlap的部分merge掉。
一開始還很克難的想說用lower_bound來判斷頭跟尾要插入的區間是否相同，後來發現這樣實在有太多例外判斷需要寫了。
濃縮最後解題關鍵如下：

Q: 假設有兩個區間: A(s1, e1)、B(s2, e2)要如何判斷A跟B有無重疊？
A: 若s1<=s2，則若且唯若e1>=s2時會重疊。
白話來說，就是我比你早開始，你要趕在我結束之前開始我們才會碰到啦！至於如果我們碰到了，要把我們兩個的區間合併起來，那就是看誰比較晚結束。
翻譯成這個題目的解法，就是先照start的時間排好，接下來比較前面的結束時間有沒有晚於等於下一個開始時間，如果沒有的話就是不重複，前面的interval可以安心加入解答中；如果有的話就有重複，把結束時間更新成兩者之間比較後面的，就好了。

所以這前後區間會不會overlap系列的解題關鍵如下，掌握到這點瞬間就簡單多了：

先按照頭去sort，再一個個檢查後面的頭有沒有<=前面的尾

我的程式碼如下，有很多冗餘的部分，沒有去優化程式碼，可以再往下參考官方解XD

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> ans = {};
            
        // sort by the begin
        sort(intervals.begin(), intervals.end());
        
        // record current intervals numbers and the latest end.
        int interNums = 0;
        int curEnd = intervals[0][1];

        // add the first one
        ans.push_back({intervals[0]});
        
        // check if the latter intervals starts before the former end
        for(int i=1; i<intervals.size();++i){
            // overlaps=> update intervals
            if(intervals[i][0]<= curEnd){
                // the ends must also be checked
                curEnd = max(curEnd, intervals[i][1]);
                ans[interNums][1] = curEnd;
            } // no overlaps=> insert intervals to answer
            else{
                ans.push_back(intervals[i]);
                curEnd = intervals[i][1];
                ++interNums;
            }
        }
        return ans;
    }
};

時間複雜度會是O(nlogn)，因為sorting需要O(nlogn)，而後面遍歷一個個檢查的動作則是O(n)。

官方解如下，整個code比較簡潔~ 可以看到我上面的code有很多冗餘的地方，例如說vector的最後一個可以用back()來取，就不用動用interNums來記錄了，還有我初始化加入第一組解的部分也可以用條件判斷來取代。

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end());

        vector<vector<int>> merged;
        for (auto interval : intervals) {
            // if the list of merged intervals is empty or if the current
            // interval does not overlap with the previous, simply append it.
            if (merged.empty() || merged.back()[1] < interval[0]) {
                merged.push_back(interval);
            }
            // otherwise, there is overlap, so we merge the current and previous
            // intervals.
            else {
                merged.back()[1] = max(merged.back()[1], interval[1]);
            }
        }
        return merged;
    }
};

結語

接下來可能可以來個經典系列題，每天就可以變形一點快樂解相關題目XD 或是來個easy秒殺系列~