区间合并-贪心

反复遇到，因此做个笔记，思想不难，所以直接看注释就够了。

题目

LC-56： 56. 合并区间 - 力扣（LeetCode）

Java 代码

class Solution {
    public int[][] merge(int[][] intervals) {
        //1.按照左端点排序
        Arrays.sort(intervals, (v1, v2) -> v1[0] - v2[0]);

        int[][] res = new int[intervals.length][2];  //存最终合并后的区间
        int idx = -1;   //第index个区间序号

        for(int[] interval : intervals){
            //初始时idx = -1，无区间；或者 上一个区间右端点小于当前区间的左端点，应该新加一个区间
            if(idx == -1 || interval[0] > res[idx][1]){
                res[++idx] = interval;
            }else {
                //否则就是区间端点有重叠，需要合并右端点(更新当前合并后区间的右端点)
                res[idx][1] = Math.max(res[idx][1], interval[1]);
            }
        }
        return Arrays.copyOf(res, idx + 1);   
        //这里为什么要拷贝一个大小为idx + 1的数组？ 
        /**
        因为最后合并区间的个数肯定是小于等于原区间个数的，而创建的临时数组res的大小就是原区间个数，如果最后合并后的区间个数小了，则会出现[0, 0]的情况。
        且个数为 idx + 1个区间，0 --> idx 个
         */
    }
}

C++代码

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> ans;

        sort(intervals.begin(), intervals.end(), [](vector<int>& a, vector<int>& b){return a[0] < b[0];});  //按照左端点，递增排序

        int st = -1, ed = -1;
        int tmp[2]={0};

        for(auto interval : intervals){
            if(ed < interval[0]){
                //区间右端点无法覆盖下一个区间，所以是个新区间(除了开始的默认区间-1，-1)
                tmp[0] = st, tmp[1] = ed;
                if(st != -1) ans.push_back({tmp[0], tmp[1]});

                //然后更新辅助区间为下一区间
                st = interval[0], ed = interval[1];
            }else {
                //否则能覆盖，更新最大覆盖范围
                ed = max(ed, interval[1]);
            }
        }
        if(st != -1){
            //最后一个区间，由于没有参照物，所以只能判断是否为空，不为空集合则放入答案数组
            ans.push_back({st, ed});
        }
        return ans;
    }
};