【LeetCode】T56 合并区间

给出一个区间的集合,请合并所有重叠的区间。

示例 1:

输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

特殊的用例:
[3,4][1,0] (后面的会插到前面或中间,不是简单的末尾合并)
[1,4][2,3] (后面的会并入前一个里面)

思路:创建res,每次往里面插入一个新的区间,然后和res尾部的合并(最后一点有优化)

  • [1][4] [4][5]首先就是最简单的并入
    • res[len-2][1] = res[len-1][1];
  • [1,4][2,3]后面的直接并入前一个
    • res[len-2] = res[len-1];
  • 提交了一次后 GG,出错的用例如下:
    • [3,4][1,0](后面的会插到前面或中间,不是简单的末尾合并)
  • 于是思考了一下如何插入到中间,巴拉巴拉半天想想,觉得太复杂了!看了下评论区,看到了 先排序 的方法,恍然大悟。
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if(intervals.size() < 2)
            return intervals;

        // 每次往res内添加一组区间,动态维护res,而不在原数组上维护。
        vector<vector<int>> res;
        // 必须先排序,否则res尾部插入[0,1]这种 “会在中间合并的数组”,会异常麻烦
        sort(intervals.begin(), intervals.end());
        
        res.push_back(intervals[0]);

        // 每次往res尾部推入一个区间,有合并就改变末尾推出一个
        for (int i = 1; i < intervals.size(); i++) { // [][]
            res.push_back(intervals[i]);
            int len = res.size();
            // 合并操作
            if(res[len-1][1] <= res[len-2][1]) // [1,4][2,3],只比较后面因为前面已经排序排好了
                res.pop_back();
            else
                if(res[len-1][0] <= res[len-2][1]){
                    if(res[len-1][0] <= res[len-2][0]){// [2,3][2,4]
                        res[len-2] = res[len-1];// 倒数第二替换为倒数第一
                        res.pop_back();
                    }
                    else{ // [1,3][2,4] 正常k合并
                        res[len-2][1] = res[len-1][1];
                        res.pop_back();
                    }
                }
        }
        return res;
    }
};

本文链接:https://ariser.cn/index.php/archives/394/
本站文章采用 知识共享署名4.0 国际许可协议进行许可,请在转载时注明出处及本声明!