开发者社区> 流楚丶格念> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

435. Non-overlapping Intervals (Medium)

简介: 435. Non-overlapping Intervals (Medium)
+关注继续查看

435. Non-overlapping Intervals (Medium)


题目描述


给定多个区间,计算让这些区间互不重叠所需要移除区间的最少个数。起止相连不算重叠。


输入输出样例


输入是一个数组,数组由多个长度固定为 2 的数组组成,表示区间的开始和结尾。输出一个整数,表示需要移除的区间数量。


Input: [[1,2], [2,4], [1,3]]
Output: 1


在这个样例中,我们可以移除区间 [1,3],使得剩余的区间 [[1,2], [2,4]] 互不重叠。


题解


在选择要保留区间时,区间的结尾十分重要:选择的区间结尾越小,余留给其它区间的空间就越大,就越能保留更多的区间。因此,我们采取的贪心策略为,优先保留结尾小且不相交的区间。


具体实现方法为,先把区间按照结尾的大小进行增序排序,每次选择结尾最小且和前一个选择的区间不重叠的区间。我们这里使用 C++ 的Lambda,结合 std::sort() 函数进行自定义排序。


在样例中,排序后的数组为 [[1,2], [1,3], [2,4]]。按照我们的贪心策略,首先初始化为区间[1,2];由于 [1,3] 与 [1,2] 相交,我们跳过该区间;由于 [2,4] 与 [1,2] 不相交,我们将其保留。因此最终保留的区间为 [[1,2], [2,4]]。


代码


class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if(intervals.empty())
            return 0;
        int size=intervals.size();
        // 从小到大排列
        sort(intervals.begin(),intervals.end(),[](vector<int> a,vector<int> b){
            return a[1]<b[1];
        });
                int count=0;
        int prev=intervals[0][1];
        for(int i=1;i<size;i++)
        {
            // 如果第二个区间的最小边界 小于 总的最大  说明有重合 丢弃  
            if(prev>intervals[i][0])
            {
                count++;
            }
            else{
                // 大于就让该边界的最大值等于 总边界的最小
                prev=intervals[i][1];
            }
        }
        return count;
    }
};

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
7月份“PolarDB-X测评”活动获奖名单
7月份“PolarDB-X测评”活动获奖名单
67 0
第一章 SDN介绍 (附件2)【SDN&NFV基础、云计算】(一)
第一章 SDN介绍 (附件2)【SDN&NFV基础、云计算】(一)
53 0
第一章 Slenium2-Java 自动化测试基础
    都是一些最基础的知识点。 一:软件测试分类 1)单元测试:单元测试(或模块测试)是对程序中的单个子程序或具有独立功能的代码段进行测试的过程。2)集成测试:集成测试是在单元测试的基础上,先通过单元模块组装成系统或子系统,再进行测试。
1089 0
opengl 教程(24) shadow mapping (2)
  原帖地址:http://ogldev.atspace.co.uk/www/tutorial24/tutorial24.html        本篇教程中,我们通过shadowmap来实现阴影渲染。
883 0
SAP Netweaver 'SAPHostControl' Service Remote Code Execution Vulnerability
http://downloads.securityfocus.com/vulnerabilities/exploits/55084.
732 0
+关注
流楚丶格念
csdn平台优质创作者,51cto TOP博主,360图书馆科技博主,燕山大学目前大三在读,日拱一卒,功不唐捐,加油!!!
1010
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载