当前位置:网站首页>905. 区间选点(贪心)
905. 区间选点(贪心)
2022-08-10 18:23:00 【一条小小yu】
给定 NN 个闭区间 [ai,bi][ai,bi],请你在数轴上选择尽量少的点,使得每个区间内至少包含一个选出的点。
输出选择的点的最小数量。
位于区间端点上的点也算作区间内。
输入格式
第一行包含整数 NN,表示区间数。
接下来 NN 行,每行包含两个整数 ai,biai,bi,表示一个区间的两个端点。
输出格式
输出一个整数,表示所需的点的最小数量。
数据范围
1≤N≤1051≤N≤105,
−109≤ai≤bi≤109−109≤ai≤bi≤109输入样例:
3 -1 1 2 4 3 5
输出样例:
2
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n;
struct Range
{
int l, r;
bool operator< (const Range &W)const
{
return r < W.r;
}
}range[N];
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) scanf("%d%d", &range[i].l, &range[i].r);
sort(range, range + n);
int res = 0, ed = -2e9;
for (int i = 0; i < n; i ++ )
if (ed < range[i].l)
{
res ++ ;
ed = range[i].r;
}
printf("%d\n", res);
return 0;
}
边栏推荐
猜你喜欢
随机推荐
基于GAMS的电力系统优化分析
关于技术分享的思考
Xilinx FPGA收发器参考时钟设计应用
Toronto Research Chemicals农药检测丨Naled-d6
友邦人寿可观测体系设计与落地
stm32中的CAN通讯列表模式配置解析与源码
NPDP|传统行业产品经理如何进行能力提升?
Mysql index, transaction and storage engine
智能出价策略如何影响广告效果?
基于 RocksDB 实现高可靠、低时延的 MQTT 数据持久化
Interview Question 04.12. Summation Path-dfs+Auxiliary Array Method
6-11 Preorder output leaf nodes (15 points)
CSV(Comma-Separate-Values)逗号分隔值文件
redis.exceptions.DataError: Invalid input of type: ‘dict‘. Convert to a byte, string or number first
消息队列初见:一起聊聊引入系统mq 之后的问题
120Hz OLED拒绝“烧屏”!华硕无双全能轻薄本
类型和id对应的两个数组
FPGA工程师面试试题集锦91~100
【2011】【论文笔记】用THz-TDS观察水树——
【FAQ】OpenHarmony与HarmonyOS的有什么区别?