leetcode归并排序_如何进行区间筛选

leetcode归并排序_如何进行区间筛选以数组 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

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

以数组 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

题解
相对0坐标进行排序,然后贪心即可。

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

        return res;
    }
};
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/169160.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • WPF实现选项卡效果(1)——使用AvalonDock

    WPF实现选项卡效果(1)——使用AvalonDock简介  公司最近一个项目,软件采用WPF开发,需要实现类似于VS的选项卡(或者是浏览器的选项卡)效果。搜寻诸多资料后,发现很多同仁推荐AvalonDock这款开源控件。在其官方地址下载源码和Demo后,对其进行了初步的研究,初步实现了预期效果。  完整系列  ●第一部分  ●第二部分  ●第三部分  在Git中下载工程源码AvalonDocking的结构树  在下载的Dem

  • SSD原理解读-从入门到精通「建议收藏」

    SSD原理解读-从入门到精通「建议收藏」SSD原理解读-从入门到精通

  • java全局变量和静态变量的区别_java局部静态变量

    java全局变量和静态变量的区别_java局部静态变量全局变量和局部变量的简介:1、全局变量:描述对象有什么(在类中定义),类中所有方法都可以使用。2、局部变量:临时保存数据(在类的方法中定义),只能在当前方法中使用。全局变量和局部变量的区别:1、作用域不同全局变量=整个类中可用局部变量=该方法内可用2、初始值不同全局变量=有初始值局部变量=无初始值3、声明上不同全局变量=在一个类中不允许声明同名变量局部变量=在一个方…

  • redis 乐观锁_用了乐观锁还需要事物吗

    redis 乐观锁_用了乐观锁还需要事物吗文章目录GeospatialHyperloglogBitmapsRedis事务悲观锁和乐观锁JedisSpringboot继承RedisGeospatial存储地理位置的数据结构应用场景朋友的定位,附近的人,打车距离计算Geospatial底层使用的是Zset127.0.0.1:6379> geoadd city 116.23 40.22 beijing 添加一个数据127.0.0.1:6379> geoadd city 121.47 31.23 shanghai 118.77

  • Idea激活码永久有效Idea2018.3.6激活码教程-持续更新,一步到位

    Idea激活码永久有效Idea2018.3.6激活码教程-持续更新,一步到位Idea激活码永久有效2018.3.6激活码教程-Windows版永久激活-持续更新,Idea激活码2018.3.6成功激活

  • Landsat 8卫星波段介绍以及波段组合[通俗易懂]

    Landsat 8卫星波段介绍以及波段组合[通俗易懂]Landsat8波段介绍: Landsat8 波段名称 BandName 波长范围(µm) Bandwidth 空间分辨率(m) Resolution 陆地成像仪:OperationalLandImager(OLI) Band1Coastal(海岸波段,可见) 0.43–0.45 30 Band2Blue(蓝波段

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号