题目描述
给定 N 个闭区间 [ai,bi],请你在数轴上选择尽量少的点,使得每个区间内至少包含一个选出的点。
输出选择的点的最小数量。
位于区间端点上的点也算作区间内。
输入格式
第一行包含整数 N,表示区间数。
接下来 N 行,每行包含两个整数 ai,bi,表示一个区间的两个端点。
输出格式
输出一个整数,表示所需的点的最小数量。
数据范围
1≤N≤105,
−109≤ai≤bi≤109
样例
输入样例:
3
-1 1
2 4
3 5
输出样例:
2
算法1
(贪心) $O(n)$
我们可以按照区间右端点位置从小到大进行排序,然后去寻找那些没有相交公共点的区间,有序我们的排序是从小到大的,所以我们可以一次找到类似于下图的区间
当推出了这种类型的区间方式之后,其区间数量就是我们要找的最小的点的数量
时间复杂度
参考文献
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int n;
struct range
{
int l,r;
bool operator < (const range &W)const//重载运算符
{
return this->r<W.r;
}
}ranges[N];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
int a,b;
cin>>a>>b;
ranges[i]={a,b};//读入
}
sort(ranges+1,ranges+n+1);//排序
int ed=-2e9,ans=0;
for(int i=1;i<=n;i++)
{
if(ranges[i].l>ed)//如果找到了下一个不相交的区间,就更新一下
{
ed=ranges[i].r;
ans++;
}
}
cout<<ans<<endl;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla