力扣56.合并区间

题目描述

题目链接56. 合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

示例 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] 可被视为重叠区间。

提示：

• 1 <= intervals.length <= 104
• intervals[i].length == 2
• 0 <= starti <= endi <= 104

思路解析

        先将数组根据每个元素的起始点进行排序，然后我们只需要比较后一个元素的起始点与前一个元素的终点大小，如果大于的话说明没有重复区间，反之有重复区间，此时将前一个元素与后一个元素进行合并，注意还需要判断前一个元素的终点与后一个元素的终点大小，如果大于的话还需要修改后一个元素的终点，否则会丢失前一个元素的一部分区间。

        当没有重复区间的时候就可以将前一个数组放入答案数组中，这样做会少放最后一个区间，所以在遍历完数组后要再将最后一个区间放入答案数组中。

        注意：如果将比较器在类中定义的话，要将比较器设置为静态成员函数。还可以将比较器用lambda表达式实现。

代码实现

bool cmp(vector<int>A,vector<int>B){
        return A[0]<B[0];
}
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& vec) {
        vector<vector<int>> ans;
        sort(vec.begin(),vec.end(),cmp);//用每个元素的起始点从小到大排序
        for(int i=1;i<vec.size();i++){//遍历数组
            if(vec[i][0]<=vec[i-1][1]){//如果该数组开始值比前一个数组结束值小，则有重复区间
                vec[i][0]=vec[i-1][0];//将该数组与前一个数组合并，前一个数组不需要再管了
                if(vec[i][1]<vec[i-1][1])vec[i][1]=vec[i-1][1];
            }
            else ans.push_back(vec[i-1]);//当没有重复区间把前一个数组放入答案数组中
        }
        ans.push_back(vec[vec.size()-1]);//把最后一个区间放入答案数组
        return ans;
    }
};

原文地址：https://blog.csdn.net/2301_80505422/article/details/144356411

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！