C++ 贪心 区间问题 最大不相交区间数

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

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

输入格式
第一行包含整数 N
,表示区间数。

接下来 N
行,每行包含两个整数 ai,bi
,表示一个区间的两个端点。

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

数据范围
1≤N≤105
,
−109≤ai≤bi≤109
输入样例:
3
-1 1
2 4
3 5
输出样例:
2
首先这样选出来的的区间是没有交集的。
在这里插入图片描述
(1)这种选法一定是一种可行的选法。Ans≥cnt
(2)根据上一题C++ 贪心 区间问题 区间选点得出先选择的点覆盖掉了所有的区间。假如Ans > cnt,则至少还存在1个这样的区间可以选择,产生矛盾。则Ans ≤cnt。
证毕。

代码是一样的:

#include <iostream>
#include <algorithm>using namespace std;const int N = 100010;int n;struct Range
{int l, r;bool operator< (Range w){return r < w.r;}
}range[N];int main ()
{scanf("%d", &n);for(int i = 0; i < n; i ++ ){int l, r;scanf("%d%d", &l, &r);range[i] = {l, r};}sort(range, range + n);int res = 0, ed = -2e9; // res是答案,ed是上一个点的下标,因为一开始的时候一个点都没有选,赋值为负无穷for(int i = 0; i < n; i ++ ) // 枚举所有的区间{if(range[i].l > ed) // 如果说当前区间的左端点严格大于上一个选出来的右端点,就更新点{res ++;ed = range[i].r;}}printf("%d\n", res);return 0;
}

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

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

相关文章

Transformer的PyTorch实现之若干问题探讨(二)

在《Transformer的PyTorch实现之若干问题探讨&#xff08;一&#xff09;》中探讨了Transformer的训练整体流程&#xff0c;本文进一步探讨Transformer训练过程中teacher forcing的实现原理。 1.Transformer中decoder的流程 在论文《Attention is all you need》中&#xff0…

阿里云游戏服务器多少钱一个月?

阿里云游戏服务器租用价格表&#xff1a;4核16G服务器26元1个月、146元半年&#xff0c;游戏专业服务器8核32G配置90元一个月、271元3个月&#xff0c;阿里云服务器网aliyunfuwuqi.com分享阿里云游戏专用服务器详细配置和精准报价&#xff1a; 阿里云游戏服务器租用价格表 阿…

【QT+QGIS跨平台编译】之三十一:【FreeXL+Qt跨平台编译】(一套代码、一套框架,跨平台编译)

文章目录 一、FreeXL介绍二、文件下载三、文件分析四、pro文件五、编译实践一、FreeXL介绍 【FreeXL跨平台编译】:Windows环境下编译成果(支撑QGIS跨平台编译,以及二次研发) 【FreeXL跨平台编译】:Linux环境下编译成果(支撑QGIS跨平台编译,以及二次研发) 【FreeXL跨平台…

Linux基础-配置网络

Linux配置网络的方式 1.图形界面 右上角-wired-配置 点加号-新建网络配置文件2.NetworkManager工具 2.1用图形终端nmtui 1.新建网络配置文件add 1.指定网络设备的类型Ethernet 2.配置网络配置文件的名称&#xff0c;名称可以有空格 3.配置网络配置文件对应的物理网络设备的…

清平乐-春风丽日

今天&#xff0c;是2024年农历除夕日&#xff0c;远方家人已于昨夜风尘扑扑地倦鸟归巢&#xff0c;团聚过龙年&#xff0c;今晨酣睡未起。老龄笔者心情极佳&#xff0c;一夜好梦醒来&#xff0c;推窗仰头展望苍穹&#xff0c;喜上心头&#xff1a;啊&#xff01;接连几天的小雨…

如何在 Mac 上恢复永久删除的文件:有效方法

您是否错误地从 Mac 中删除了某个文件&#xff0c;并且确信它已经永远消失了&#xff1f;好吧&#xff0c;你可能错了。即使您认为已永久删除计算机上的数据&#xff0c;仍有可能将其恢复。 在本文中&#xff0c;您将了解如何在 Mac 上恢复永久删除的文件&#xff0c;并了解增…

vim常用命令以及配置文件

layout: article title: “vim文本编译器” vim文本编辑器 有三种模式: 命令模式 文本模式, 末行模式 vim命令大全 - 知乎 (zhihu.com) 命令模式 插入 i: 切换到输入模式&#xff0c;在光标当前位置开始输入文本。 a: 进入插入模式&#xff0c;在光标下一个位置开始输入文…

C++多线程:this_thread 命名空间

std::this_thread 是 C 标准库中提供的一个命名空间&#xff0c;它包含了与当前线程相关的功能。这个命名空间提供了许多与线程操作相关的工具&#xff0c;使得在多线程环境中更容易进行编程。 源码类似于如下&#xff1a; namespace std{namespace this_thread{//...........…

Swift Combine 管道 从入门到精通三

Combine 系列 Swift Combine 从入门到精通一Swift Combine 发布者订阅者操作者 从入门到精通二 1. 用弹珠图描述管道 函数响应式编程的管道可能难以理解。 发布者生成和发送数据&#xff0c;操作符对该数据做出响应并有可能更改它&#xff0c;订阅者请求并接收这些数据。 这…

《学成在线》微服务实战项目实操笔记系列(P1~P83)【上】

史上最详细《学成在线》项目实操笔记系列【上】&#xff0c;跟视频的每一P对应&#xff0c;全系列12万字&#xff0c;涵盖详细步骤与问题的解决方案。如果你操作到某一步卡壳&#xff0c;参考这篇&#xff0c;相信会带给你极大启发。 一、前期准备 1.1 项目介绍 P2 To C面向…

vue3 之 商城项目—详情页

整体认识 路由配置 准备组件模版 <script setup></script><template><div class"xtx-goods-page"><div class"container"><div class"bread-container"><el-breadcrumb separator">">&…

引用论文bib信息解析,查看年、卷、期

2022,53(01):69-74 53卷 01期 volume{29},卷 number{},

SpringBoot配置文总结

官网配置手册 官网&#xff1a;https://spring.io/ 选择SpringBoot 选择LEARN 选择 Application Properties 配置MySQL数据库连接 针对Maven而言&#xff0c;会搜索出两个MySQL的连接驱动。 com.mysql mysql-connector-j 比较新&#xff0c;是在mysql mysql-connect…

2.6:冒泡、简选、直插、快排,递归,宏

1.冒泡排序、简单选择排序、直接插入排序、快速排序(升序) 程序代码&#xff1a; 1 #include<stdio.h>2 #include<string.h>3 #include<stdlib.h>4 void Bubble(int arr[],int len);5 void simple_sort(int arr[],int len);6 void insert_sort(int arr[],in…

ArcGIS Pro 按照字段进行融合或拆分

ArcGIS Pro 按字段融合 在ArcGIS Pro中&#xff0c;通过使用“融合”工具可以轻松地合并具有相同字段的图层。 步骤一&#xff1a;打开ArcGIS Pro 启动ArcGIS Pro应用程序&#xff0c;确保您已经登录并打开您的项目。 步骤二&#xff1a;添加图层 将包含相同字段的图层添加到…

2024牛客寒假算法基础集训营1(视频讲解全部题目)

2024牛客寒假算法基础集训营1&#xff08;题目全解&#xff09; ABCDEFGHIJKLM 2024牛客寒假算法基础集训营1&#xff08;视频讲解全部题目&#xff09; A #include<bits/stdc.h> #define endl \n #define deb(x) cout << #x << " " << …

探索Xposed框架:个性定制你的Android体验

探索Xposed框架&#xff1a;个性定制你的Android体验 1. 引言 在当今移动设备市场中&#xff0c;Android系统作为最受欢迎的操作系统之一&#xff0c;其开放性和可定制性备受用户青睐。用户希望能够根据个人喜好和需求对其设备进行定制&#xff0c;以获得更符合自己习惯的使用…

大模型基础架构的变革:剖析Transformer的挑战者(下)

上一篇文章中&#xff0c;我们介绍了UniRepLKNet、StripedHyena、PanGu-π等有可能会替代Transformer的模型架构&#xff0c;这一篇文章我们将要介绍另外三个有可能会替代Transformer的模型架构&#xff0c;它们分别是StreamingLLM、SeTformer、Lightning Attention-2&#xff…

LabVIEW伺服阀性能参数测试

LabVIEW伺服阀性能参数测试 伺服阀作为电液伺服系统中的核心元件&#xff0c;其性能参数的准确测试对保证系统整体性能至关重要。开发了一种基于LabVIEW软件开发的伺服阀性能参数测试系统&#xff0c;提高测试的自动化程度和精确性&#xff0c;同时降低操作复杂度和成本。 传…

Python中使用opencv-python库进行颜色检测

Python中使用opencv-python库进行颜色检测 之前写过一篇VC中使用OpenCV进行颜色检测的博文&#xff0c;当然使用opencv-python库也可以实现。 在Python中使用opencv-python库进行颜色检测非常简单&#xff0c;首选读取一张彩色图像&#xff0c;并调用函数imgHSV cv2.cvtColor…