[Day 17] Leetcode 56. Merge Intervals (C++)

前言

连假结束加班加起来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秒杀系列~