贪心算法|435.无重叠区间
力扣题目链接
class Solution {
public:// 按照区间右边界排序static bool cmp (const vector<int>& a, const vector<int>& b) {return a[1] < b[1];}int eraseOverlapIntervals(vector<vector<int>>& intervals) {if (intervals.size() == 0) return 0;sort(intervals.begin(), intervals.end(), cmp);int count = 1; // 记录非交叉区间的个数int end = intervals[0][1]; // 记录区间分割点for (int i = 1; i < intervals.size(); i++) {if (end <= intervals[i][0]) {end = intervals[i][1];count++;}}return intervals.size() - count;}
};
写算法题是需要集中注意力,静下心用心去写的。
如果你浮躁的话会发现理解不了,你如果静下心一步一步去画理清自己思路其实还是很容易的。
代码随想录 (programmercarl.com)
思路
相信很多同学看到这道题目都冥冥之中感觉要排序,但是究竟是按照右边界排序,还是按照左边界排序呢?
其实都可以。主要就是为了让区间尽可能的重叠。
我来按照右边界排序,从左向右记录非交叉区间的个数。最后用区间总数减去非交叉区间的个数就是需要移除的区间个数了。
此时问题就是要求非交叉区间的最大个数。
这里记录非交叉区间的个数还是有技巧的,如图:

区间,1,2,3,4,5,6都按照右边界排好序。
当确定区间 1 和 区间2 重叠后,如何确定是否与 区间3 也重贴呢?
就是取 区间1 和 区间2 右边界的最小值,因为这个最小值之前的部分一定是 区间1 和区间2 的重合部分,如果这个最小值也触达到区间3,那么说明 区间 1,2,3都是重合的。
接下来就是找大于区间1结束位置的区间,是从区间4开始。那有同学问了为什么不从区间5开始?别忘了已经是按照右边界排序的了。
区间4结束之后,再找到区间6,所以一共记录非交叉区间的个数是三个。
总共区间个数为6,减去非交叉区间的个数3。移除区间的最小数量就是3。
自己的理解:
刚开始一直静不下心去写,然后有些地方看不懂。
后来自己去看视频静下心去理解,梳理自己的思路。

卡哥视频讲的是按左区间排序,但是这个代码答案是右区间排序哦!
而且计算的count还是不重叠部分的。
1.注意i是从1开始,这样才能和前面的有所比较
2.判断区间是否重叠
上一个区间的右区间 <= 当前区间的左区间 (不重叠)
else 重叠
因为计算的是不重叠的count
所以不重叠count++
更改end

理解后独自敲的代码,语法不熟练啊!
还有可笑的错误!
相关文章:
贪心算法|435.无重叠区间
力扣题目链接 class Solution { public:// 按照区间右边界排序static bool cmp (const vector<int>& a, const vector<int>& b) {return a[1] < b[1];}int eraseOverlapIntervals(vector<vector<int>>& intervals) {if (intervals.siz…...
C++的并发世界(七)——互斥锁
0.死锁的由来 假设有两个线程T1和T2,它们需要对两个互斥量mtx1和mtx2进行访问。而且需要按照以下顺序获取互斥量的所有权: -T1先获取mte1的所有权,再获取mt2的所有权。 -T2先获取 mtx2的所有权。再铁取 mtx1的所有权。 如果两个线程同时执行,…...
NI-LabView的DAQ缺少或丢失的解决办法(亲测有效)
DAQmx在Labview中不显示或缺失 问题:在NI Packasge Manager安装完DAQ后在labview中不显示控件解决办法 问题:在NI Packasge Manager安装完DAQ后在labview中不显示控件 在打开测量I/O时,见不到 DAQmx,或者在Express中见不到DAQ助手…...
cesium 调整3dtiles的位置 世界坐标下 相对坐标下 平移矩阵
cesium调整3dtiles的位置用到的是平移矩阵,原理是在世界坐标系中用偏移点减去原始点得到一个平移向量,再根据这个向量得到平移矩阵。 原始点:一般是模型的中心点位置,可通过模型的包围盒得到偏移点:可分为两种情况&…...
flutter跑通腾讯云直播Demo
运行示例 前提条件 要求java jdk 11版本 并且配置到了环境变量 重要 要求flutter 版本 2.8.0 并且配置到了环境变量 重要 要求dart-sdk版本2.15 并且配置到了环境变量 重要 您已 注册腾讯云 账号,并完成 实名认证。 申请 SDKAPPID 和 SECRETKEY 登录实时音视频控…...
飞机降落蓝桥杯[2023蓝桥省赛B组]
2023蓝桥省赛B组 B题 飞机降落 题解 标准深搜板子题,难度不大 #include<bits/stdc.h> using namespace std; #define MAX 10 struct node{int t,d,l;//t:飞机到达时间 d:飞机最大盘旋时间 l:飞机降落所需时间bool v;//标记此架飞机是否被搜索过 用于剪枝 };…...
如何动态渲染HTML内容?用v-html!
🤍 前端开发工程师、技术日更博主、已过CET6 🍨 阿珊和她的猫_CSDN博客专家、23年度博客之星前端领域TOP1 🕠 牛客高级专题作者、打造专栏《前端面试必备》 、《2024面试高频手撕题》 🍚 蓝桥云课签约作者、上架课程《Vue.js 和 E…...
EFcore 6 连接oracle19 WinForm vs2022
用EFcore访问Oracle,终于不需要Oracle的什么安装包了,直接在VS2022中就可以轻松搞定。在csdn上看到一哥们的帖子,测试了一下,发现很方便。使用的场景是:VS2022中EFcore6。经过测试,同 Navicat Premium 16比…...
(delphi11最新学习资料) Object Pascal 学习笔记---第9章第2节(finally代码块)
9.2 finally 代码块 还有第四个用于异常处理的关键字,我已经提到过,但到目前为止还没有使用过,那就是 finally。finally块用于执行一些应始终执行的操作(通常是清理操作)。事实上,无论是否发生异常&…...
220 基于matlab的考虑直齿轮热弹耦合的动力学分析
基于matlab的考虑直齿轮热弹耦合的动力学分析,输入主动轮、从动轮各类参数,考虑润滑油温度、润滑油粘度系数等参数,输出接触压力、接触点速度、摩擦系数、对流传热系数等结果。程序已调通,可直接运行。 220直齿轮热弹耦合 接触压力…...
Intrigue Core:一款功能强大的攻击面枚举引擎
关于Intrigue Core Intrigue Core是一款功能强大的开源攻击面枚举引擎,该工具可以帮助广大研究人员更好地管理应用程序的攻击面。 Intrigue Core集成了各种各样的安全数据源,可以将这些数据提取到标准化的对象模型中,并通过图形数据库跟踪关…...
【精品PPT】智慧路灯大数据平台整体建设实施方案(免费下载)
1、知识星球下载: 如需下载完整PPTX可编辑源文件,请前往星球获取:https://t.zsxq.com/19QeHVt8y 2、免费领取步骤: 【1】关注公众号 方案驿站 【2】私信发送 【智慧路灯大数据平台】 【3】获取本方案PDF下载链接,直…...
idea 中运行spring boot 项目报 Command line is too long的解决办法。
Command line is too long 在这里选择edit configures 选择shrten command line , 选择 jar manifest 运行即可。...
Windows终端添加git bash
环境:windows11 终端:windows terminal git bash默认的界面不太好看,添加到终端会比较好用 步骤 打开 windows terminal,在向下箭头 点击 设置左侧栏 点击 “添加新配置文件”,如下图配置,主要修改项&…...
【方法】PDF密码如何取消?
对于重要的PDF文件,很多人会设置密码保护,那后续不需要保护了,如何取消密码呢? 今天我们来看看,PDF的两种密码,即“限制密码”和“打开密码”,是如何取消的,以及忘记密码的情况要怎…...
怎么开发一个预约小程序_一键预约新体验
预约小程序,让生活更便捷——轻松掌握未来,一键预约新体验 在快节奏的现代生活中,我们总是在不断地奔波,为了工作、为了生活,不停地忙碌着。然而,在这繁忙的生活中,我们是否曾想过如何更加高效…...
JavaScript_注释数据类型
JavaScript_语法_注释&数据类型: 1.2注释: 1.单行注释://注释内容 2.多行注释:/*注释内容*/ 1.3数据类型: 1.原始数据类型(基本数据类型):(只有这五种) 1.number:数字…...
蓝桥杯2020年第十一届省赛 CC++ 研究生组2.0
约数个数 #include<iostream> #include<cmath> using namespace std; int main(){int n 78120, ans 0, sqr sqrt(n);for(int i 1; i < sqr; i){if(n % i 0){ans;//printf("%d,", i);if(i * i ! n) {ans;//printf("%d,", n / i);}}}//…...
SOCKS5代理、代理IP、跨界电商、游戏技术与网络安全的综合探讨
在全球经济一体化的大背景下,"出海"已成为许多企业尤其是电商和游戏行业的重要战略方向。然而,随着企业业务的扩展到海外市场,网络安全、数据隐私和内容访问等问题也随之而来。本文将深入探讨SOCKS5代理、代理IP在跨界电商和游戏行…...
关于HTTP1.0、1.1、1.x、2.0、3.0与HTTPS之间的理解
关于HTTP1.0、1.1、1.x、2.0、3.0与HTTPS之间的理解 HTTP的由来 HTTP是Hyper Text Transfer Protocol(超文本传输协议)的缩写。它的发展是万维网协会(World Wide Web Consortium)和Internet工作小组IETF(Internet Eng…...
Cursor实现用excel数据填充word模版的方法
cursor主页:https://www.cursor.com/ 任务目标:把excel格式的数据里的单元格,按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例,…...
基于Flask实现的医疗保险欺诈识别监测模型
基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施,由雇主和个人按一定比例缴纳保险费,建立社会医疗保险基金,支付雇员医疗费用的一种医疗保险制度, 它是促进社会文明和进步的…...
【大模型RAG】Docker 一键部署 Milvus 完整攻略
本文概要 Milvus 2.5 Stand-alone 版可通过 Docker 在几分钟内完成安装;只需暴露 19530(gRPC)与 9091(HTTP/WebUI)两个端口,即可让本地电脑通过 PyMilvus 或浏览器访问远程 Linux 服务器上的 Milvus。下面…...
Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务
通过akshare库,获取股票数据,并生成TabPFN这个模型 可以识别、处理的格式,写一个完整的预处理示例,并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务,进行预测并输…...
跨链模式:多链互操作架构与性能扩展方案
跨链模式:多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈:模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展(H2Cross架构): 适配层…...
反射获取方法和属性
Java反射获取方法 在Java中,反射(Reflection)是一种强大的机制,允许程序在运行时访问和操作类的内部属性和方法。通过反射,可以动态地创建对象、调用方法、改变属性值,这在很多Java框架中如Spring和Hiberna…...
WordPress插件:AI多语言写作与智能配图、免费AI模型、SEO文章生成
厌倦手动写WordPress文章?AI自动生成,效率提升10倍! 支持多语言、自动配图、定时发布,让内容创作更轻松! AI内容生成 → 不想每天写文章?AI一键生成高质量内容!多语言支持 → 跨境电商必备&am…...
Ascend NPU上适配Step-Audio模型
1 概述 1.1 简述 Step-Audio 是业界首个集语音理解与生成控制一体化的产品级开源实时语音对话系统,支持多语言对话(如 中文,英文,日语),语音情感(如 开心,悲伤)&#x…...
浅谈不同二分算法的查找情况
二分算法原理比较简单,但是实际的算法模板却有很多,这一切都源于二分查找问题中的复杂情况和二分算法的边界处理,以下是博主对一些二分算法查找的情况分析。 需要说明的是,以下二分算法都是基于有序序列为升序有序的情况…...
是否存在路径(FIFOBB算法)
题目描述 一个具有 n 个顶点e条边的无向图,该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序,确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数,分别表示n 和 e 的值(1…...
