当前位置:网站首页>905. Interval selection
905. Interval selection
2022-08-05 03:24:00 【Hunter_Kevin】
905. 区间选点
给定 N 个闭区间 [ai,bi],请你在数轴上选择尽量少的点,使得每个区间内至少包含一个选出的点.
输出选择的点的最小数量.
位于区间端点上的点也算作区间内.
输入格式
第一行包含整数 N,表示区间数.
接下来 N 行,每行包含两个整数 ai,bi,表示一个区间的两个端点.
输出格式
输出一个整数,表示所需的点的最小数量.
数据范围
1≤N≤105,
−109≤ai≤bi≤109
输入样例:
3
-1 1
2 4
3 5
输出样例:
2
代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
typedef pair<int,int> PII;
PII a[N];
bool comp(PII x, PII y)
{
return x.second < y.second;
}
int main()
{
int n;
cin >> n;
for(int i = 0; i < n; i++)cin >> a[i].first >> a[i].second;
// Sort by the size of the right endpoint of the interval
sort(a,a+n,comp);
// Each time the right endpoint of the interval is selected as the selection point
int r = a[0].second;
int res = 1;
for(int i = 1; i < n; i++){
if(a[i].first > r){
//如果当前区间的左端点>选点 That is, the interval does not include selected points,Then update the interval boundary and the new selection point
res++;
r = a[i].second;
}//如果当前区间的左端点<=选点,then ignore the current range,Continue to judge the next interval
}
cout << res << endl;
return 0;
}
边栏推荐
- ffmpeg 枚举decoders, encoders 分析
- Countdown to 2 days|Cloud native Meetup Guangzhou Station, waiting for you!
- 开发Hololens遇到The type or namespace name ‘HandMeshVertex‘ could not be found..
- 队列题目:最近的请求次数
- [Solved] Unity Coroutine coroutine is not executed effectively
- QT: The Magical QVarient
- 腾讯云【Hiflow】新时代自动化工具
- 论治理与创新,2022 开放原子全球开源峰会 OpenAnolis 分论坛圆满落幕
- Getting Started with Kubernetes Networking
- AI + Small Nucleic Acid Drugs | Eleven Completes $22 Million Seed Round Financing
猜你喜欢
告白数字化转型时代,时速云镌刻价值新起点
dmp (dump) dump file
静态方法获取配置文件数据
Question about #sql shell#, how to solve it?
【七夕节】浪漫七夕,代码传情。将爱意变成绚烂的立体场景,给她(他)一个惊喜!(送代码)
Why is the pca component not associated
冰蝎V4.0攻击来袭,安全狗产品可全面检测
Bubble Sort and Quick Sort
The linear table lookup
Never put off till tomorrow what you can put - house lease management system based on the SSM
随机推荐
Flink 1.15.1 Cluster Construction (StandaloneSession)
YYGH-13-客服中心
思考(八十八):使用 protobuf 自定义选项,做数据多版本管理
905. 区间选点
One hundred - day plan -- -- DAY2 brush
Burp installation and proxy settings
Linux下常见的开源数据库,你知道几个?
Ffmpeg - sources analysis
队列题目:最近的请求次数
How to sort multiple fields and multiple values in sql statement
Why did they choose to fall in love with AI?
Details such as compiling pretreatment
QT language file production
冰蝎V4.0攻击来袭,安全狗产品可全面检测
rpc-remote procedure call demo
In 2022, you still can't "low code"?Data science can also play with Low-Code!
shell脚本:for循环与while循环
Simple description of linked list and simple implementation of code
Open Source License Description LGPL
A small tool to transfer files using QR code - QFileTrans 1.2.0.1