当前位置:网站首页>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;
}
边栏推荐
- sql server installation prompts that the username does not exist
- AI + Small Nucleic Acid Drugs | Eleven Completes $22 Million Seed Round Financing
- 冒泡排序与快速排序
- Physical backup issues caused by soft links
- 调用阿里云oss和sms服务
- 用Unity发布APP到Hololens2无坑教程
- How to find all fields with empty data in sql
- Kubernetes 网络入门
- dmp (dump) dump file
- Shell script: for loop and the while loop
猜你喜欢
Tencent Cloud [Hiflow] New Era Automation Tool
[Qixi Festival] Romantic Tanabata, code teaser.Turn love into a gorgeous three-dimensional scene and surprise her (him)!(send code)
Everyone in China said data, you need to focus on core characteristic is what?
链表的简单描述及代码的简单实现
引领数字医学高地,中山医院探索打造未来医院“新范式”
ASP.NET application--Hello World
Talking about data security governance and privacy computing
结构体初解
Getting Started with Kubernetes Networking
Developing Hololens encountered The type or namespace name 'HandMeshVertex' could not be found..
随机推荐
The Tanabata copywriting you want has been sorted out for you!
Everyone in China said data, you need to focus on core characteristic is what?
(十一)元类
word分栏小记
剑指Offer--找出数组中重复的数字(三种解法)
从“能用”到“好用” 国产软件自主可控持续推进
21天学习挑战赛(2)图解设备树的使用
MRTK3开发Hololens应用-手势拖拽、旋转 、缩放物体实现
如何在WordPress中添加特定类别的小工具
Use SuperMap iDesktopX data migration tool to migrate ArcGIS data
The pit of std::string::find return value
Syntax basics (variables, input and output, expressions and sequential statement completion)
presto启动成功后出现2022-08-04T17:50:58.296+0800 ERROR Announcer-3 io.airlift.discovery.client.Announcer
2022-08-04 第六小组 瞒春 学习笔记
Simple description of linked list and simple implementation of code
队列题目:最近的请求次数
沃谈小知识 |“远程透传”那点事儿
链表的简单描述及代码的简单实现
Never put off till tomorrow what you can put - house lease management system based on the SSM
Call Alibaba Cloud oss and sms services