首页 > 其他 > 详细

LeetCode 合并区间(贪心)

时间:2020-03-05 20:37:14      阅读:72      评论:0      收藏:0      [点我收藏+]

题意

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

示例

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

思路

贪心,按照每个区间的开始值,开始从小达到排序即可。

从第一个区间开始往后扫描,如果可以合并,则合并;当不能合并的时候,将已经合并的区间计入到答案中,然后从此区间继续执行本操作。

证明

排序后,对于任意的i ,j (j > i)intervals[i][1] > intervals[j][0](即第i个和第j个区间无法合并),不存在一个z(z > j),使得intervals[i][1] <= intervals[z][0](即第z个区间可以和i合并)

因为第j个区间不可以和第i个区间合并

那么intervals[i][1] < intervals[j][0]

由于排序是按照区间左端点进行排序

那么intervals[j][0] < intervals[z][0]

那么intervals[i][1] < intervals[z][0]

即第z个区间不能与第i个区间合并

代码

class Solution {
public:
    static bool cmp(vector<int> a, vector<int> b){
        return a[0] < b[0];
    }
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> ans;
        sort(intervals.begin(), intervals.end(), cmp);
        int i = 0;
        while(i < intervals.size()){
            int j = i + 1;
            for(; j < intervals.size(); j++){
                if(intervals[j][0] <= intervals[i][1]){
                    intervals[i][1] = max(intervals[j][1], intervals[i][1]);
                }   
                else{
                    break;
                }
            }
            ans.emplace_back(intervals[i]);
            i = j;
        }
        return ans;
    }
};

LeetCode 合并区间(贪心)

原文:https://www.cnblogs.com/woxiaosade/p/12422451.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!