[C++][算法基础]最大不相交区间数量(贪心 + 区间问题2)

给定 𝑁 个闭区间 [𝑎𝑖,𝑏𝑖],请你在数轴上选择若干区间,使得选中的区间之间互不相交(包括端点)。

输出可选取区间的最大数量。

输入格式

第一行包含整数 𝑁,表示区间数。

接下来 𝑁 行,每行包含两个整数 𝑎𝑖,𝑏𝑖,表示一个区间的两个端点。

输出格式

输出一个整数,表示可选取区间的最大数量。

数据范围

1≤𝑁≤10^{5},
10^{9}≤𝑎𝑖≤𝑏𝑖≤10^{9}

输入样例:
3
-1 1
2 4
3 5
输出样例:
2

代码:

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;const int N = 100010;
int n,l,r;
vector<pair<int,int>> Interval;int main(){cin>>n;for(int i = 0;i < n;i ++){cin>>l>>r;Interval.push_back({r,l});}sort(Interval.begin(),Interval.end());int res = 0, RightEnd = -2e9;for(int i = 0;i < n;i ++){int left = Interval[i].second;int right = Interval[i].first;if(left > RightEnd){res ++;RightEnd = right;}}cout<<res<<endl;return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/316646.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【算法基础实验】图论-UnionFind连通性检测之quick-union

Union-Find连通性检测之quick-union 理论基础 在图论和计算机科学中&#xff0c;Union-Find 或并查集是一种用于处理一组元素分成的多个不相交集合&#xff08;即连通分量&#xff09;的情况&#xff0c;并能快速回答这组元素中任意两个元素是否在同一集合中的问题。Union-Fi…

PHP源码_最新在线工具箱网站系统源码

项目运行截图 源码贡献 https://githubs.xyz/boot?app41 部分数据库表 SET NAMES utf8mb4; SET FOREIGN_KEY_CHECKS 0;-- ---------------------------- -- Table structure for toolbox_category -- ---------------------------- DROP TABLE IF EXISTS toolbox_category…

StarRocks x Paimon 构建极速实时湖仓分析架构实践

Paimon 介绍 Apache Paimon 是新一代的湖格式&#xff0c;可以使用 Flink 和 Spark 构建实时 Lakehouse 架构&#xff0c;以进行流式处理和批处理操作。Paimon 创新性地使用 LSM&#xff08;日志结构合并树&#xff09;结构&#xff0c;将实时流式更新引入 Lakehouse 架构中。 …

医学vr虚拟仿真综合实验教学平台为科研教学提供了坚实的基础

在兽医专业的广袤领域中&#xff0c;动物解剖学作为基石学科&#xff0c;为组织胚胎学、生理学、病理解剖学、外科手术学、临床诊断学等科研教学提供了坚实的基础。而如今&#xff0c;随着科技的飞速发展&#xff0c;我们迎来了一个全新的学习时代——3D数字动物解刨虚拟仿真实…

[iOS]使用CocoaPods发布公开库

1.检查库名是否已被占用 选择库名时&#xff0c;尽量选择具有描述性并且独特的名字&#xff0c;这不仅可以避免命名冲突&#xff0c;还可以帮助用户更好地理解库的用途和功能。 在实际创建和发布 CocoaPods 库之前&#xff0c;确实应该检查库名是否已经被占用&#xff0c;以避…

AutoCAD 2025 for mac/win:设计未来,触手可及

在数字化时代&#xff0c;设计不再局限于纸笔之间&#xff0c;而是跃然于屏幕之上&#xff0c;AutoCAD 2025正是这一变革的杰出代表。无论是Mac用户还是Windows用户&#xff0c;AutoCAD 2025都以其卓越的性能和出色的用户体验&#xff0c;成为了CAD设计绘图领域的佼佼者。 Aut…

Vuforia AR篇(三)— AR模型出场效果

目录 前言一、AR模型出场二、AR出场特效三、添加过渡效果四、效果 前言 在这个数字化日益增长的时代&#xff0c;增强现实&#xff08;AR&#xff09;技术正以前所未有的速度发展。AR模型&#xff0c;作为这一技术的核心组成部分&#xff0c;不仅改变了我们与数字世界的互动方…

【MATLAB源码-第201期】基于matlab的黏菌群优化算法(SMA)无人机三维路径规划,输出做短路径图和适应度曲线

操作环境&#xff1a; MATLAB 2022a 1、算法描述 黏菌优化算法&#xff08;Slime Mould Algorithm, SMA&#xff09;是一种新颖的启发式优化方法&#xff0c;其灵感来源于自然界中的真菌——黏菌。这种算法模拟了黏菌在寻找食物时的行为和网络形成策略。在本文中&#xff0c…

Python | Leetcode Python题解之第58题最后一个单词的长度

题目&#xff1a; 题解&#xff1a; class Solution:def lengthOfLastWord(self, s: str) -> int:ls[]for i in s.split():ls.append(i)return len(ls[-1])

【华为】NAT的分类和实验配置

【华为】NAT的分类和实验配置 NAT产生的技术背景IP地址分类NAT技术原理NAT分类静态NAT动态NATNAPTEasy IP&#xff08;PAT&#xff09;NAT Server 配置拓扑静态NAT测试抓包 动态NAT测试抓包 NAPT测试抓包 PAT测试抓包 NAT Server检测抓包 PC1PC2服务器 NAT产生的技术背景 随着…

排序算法:插入、希尔、选择、推排、冒泡、快速、归并排序

排序算法 目录 前言 一、排序的概念 1.1排序的概念 1.2 常见的排序算法 二、常见排序算法的实现 2.1 插入排序 2.2 希尔排序 2.3 选择排序 2.4 堆排序 2.5 冒泡排序 2.6 快速排序 2.6.1 hoare版本 2.6.2 前后指针版本 2.6.3 非递归版本 2.7 归并排序 归并排序 2.8 计数排序 三、…

Android视角看鸿蒙第十二课-鸿蒙的布局之相对布局RelativeContainer

Android视角看鸿蒙第十二课-鸿蒙的布局之相对布局RelativeContainer 导读 相对布局和线性、层叠布局一样都是类似于Android布局的&#xff0c;之前两篇文章已经了解线性、层叠布局的使用方法&#xff0c;这篇文章一起来学习下鸿蒙中的相对布局。 之前的文章中&#xff0c;我偶…

10.MMD 室内场景导入背景视频和灯光

导入背景视频 1. 导入人物和场景 场景是Akali’s room&#xff0c;可以在墙壁上添加视频 先添加主场景 2. 修改视频文件格式 在背景里选择导入背景视频文件 需要将mp4视频格式转化为AVI格式 方法一 先将视频导入格式工厂 点击配置 将视频编码改成DivX 再开始处理 …

数据结构八:线性表之循环队列的设计

上篇博客&#xff0c;学习了栈&#xff0c;我们可以知道他也是一种线性表&#xff0c;遵从先进后出的原则&#xff0c;在本节&#xff0c;我们进一步学习另一种线性表—队列。就像饭堂里排队打饭的的队伍&#xff0c;作为一种先进先出的线性表&#xff0c;他又有哪些特别之处呢…

敏捷之Scrum开发

目录 一、什么是 Scrum 1.1 Scrum 的定义 二、Scrum 迭代开发过程 2.1 迭代开发过程说明 2.1.1 开发方法 2.1.1.1 增量模型 2.1.1.1.1 定义 2.1.1.1.2 模型方法说明 2.1.1.2 迭代模型 2.1.1.2.1 定义 2.1.1.2.2 模型方法说明 2.1.2 迭代过程 2.1.2.1 产品需求Produ…

windows下安装onlyoffice

文章目录 1、 安装ErLang2、 安装rabbitmq3、 安装postgresql4、 安装onlyoffice(社区版) 1、 安装ErLang 下载地址&#xff1a;https://erlang.org/download/otp_win64_24.2.exe opt_wind64_24.2.exe 直接运行&#xff0c;一步一步安装 2、 安装rabbitmq 下载地址&#xf…

【003_音频开发_基础篇_Linux进程通信(20种你了解几种?)】

003_音频开发_基础篇_Linux进程通信&#xff08;20种你了解几种&#xff1f;) 文章目录 003_音频开发_基础篇_Linux进程通信&#xff08;20种你了解几种&#xff1f;)创作背景Linux 进程通信类型fork() 函数fork() 输出 2 次fork() 输出 8 次fork() 返回值fork() 创建子进程 方…

JAVA:maven-->>检查 所有依赖 与 环境 兼容

内容 为了确保你项目中的所有依赖都彼此兼容&#xff0c;并与你的环境相适应&#xff0c;你可以利用 Maven 的依赖管理功能。Maven 有助于解决、升级&#xff0c;并对齐所有库的版本&#xff0c;以避免任何不一致或冲突。以下是检查兼容性的步骤&#xff1a; ### 检查兼容性的…

Pulsar Meetup 深圳 2024 会务介绍

“ Hi&#xff0c;各位热爱 Pulsar 的小伙伴们&#xff0c;Pulsar Meetup 深圳 2024 报名倒计时啦&#xff0c;快来报名。这里汇集了腾讯、华为和谙流科技等大量 Pulsar 大咖&#xff0c;干货多多&#xff0c;礼品多多&#xff0c;不容错过啊。 ” 活动介绍 由 AscentStream 谙…

C语言:插入排序

插入排序 1.解释2.步骤3.举例分析示例结果分析 1.解释 插入排序是一种简单直观的排序算法&#xff0c;它的工作原理是通过构建有序序列&#xff0c;对于未排序数据&#xff0c;在已排序序列中从后向前扫描&#xff0c;找到相应位置并插入。插入排序在实现上&#xff0c;通常采…