题目描述
给定 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)$
这道题就是区间选点的本质思想实现,对其右端点排序,用循环从小到大一个个筛选出不相交的区间,这些不相交的区间数量就是我们要找的最大不相交区间数量
cnt:我选出来确定不相交区间的数量,ans:最大不相交区间数量
证明一下,y总思路是,证明cnt==ans,即证明cnt>=ans&&cnt<=ans
我的思路是,证明ans>=cnt&&ans!>cnt
ans既然是最大的,那么自然而然的,ans>=cnt
cnt又是我们选出来确定不相交区间的点,那么我们想确定ans个区间,最少需要ans个点,当ans>cnt的时候,仅有cnt个点无法确定ans个区间,故不成立
综上所述:ans==cnt
sort函数使用及重载运算符: https://www.cnblogs.com/junbaobei/p/10776066.html 重载运算符滑到最下面
时间复杂度
参考文献
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)$
思路是一样的,这个左端点排序仅为实现选出不相交区间的方式,好处在于不需要重载运算符
因为sort函数默认以第一个为准
时间复杂度
参考文献
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
typedef pair<int,int> PII;
int n;
PII s[N];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
int a,b;
cin>>a>>b;
s[i]={a,b};
}
sort(s+1,s+n+1);
int ans=1,R=s[1].second;//这里从一开始,直接塞进去一个,因为第一个始终是要选的
for(int i=2;i<=n;i++)
{
if(s[i].first<=R)R=min(R,s[i].second);
else
{
ans++;
R=s[i].second;
}
}
cout<<ans<<endl;
}
STL版本,vector的sort函数运用 https://www.cnblogs.com/zhouxiaosong/p/5557990.html#:~:text=sort%E6%96%B9%E6%B3%95%E6%98%AFalgorithm%E5%A4%B4%E6%96%87%E4%BB%B6%E9%87%8C%E7%9A%84%E4%B8%80%E4%B8%AA%E6%A0%87%E5%87%86%E5%87%BD%E6%95%B0%EF%BC%8C%E8%83%BD%E8%BF%9B%E8%A1%8C%E9%AB%98%E6%95%88%E7%9A%84%E6%8E%92%E5%BA%8F%EF%BC%8C%E9%BB%98%E8%AE%A4%E6%98%AF%E6%8C%89%E5%85%83%E7%B4%A0%E4%BB%8E%E5%B0%8F%E5%88%B0%E5%A4%A7%E6%8E%92%E5%BA%8F.%20%E5%B0%86sort%E6%96%B9%E6%B3%95%E7%94%A8%E5%88%B0vector%E5%92%8Cset%E4%B8%AD%E8%83%BD%E5%AE%9E%E7%8E%B0%E5%A4%9A%E7%A7%8D%E7%AC%A6%E5%90%88%E8%87%AA%E5%B7%B1%E9%9C%80%E6%B1%82%E7%9A%84%E6%8E%92%E5%BA%8F.%20%E9%A6%96%E5%85%88sort%E6%96%B9%E6%B3%95%E5%8F%AF%E4%BB%A5%E5%AF%B9%E9%9D%99%E6%80%81%E7%9A%84%E6%95%B0%E7%BB%84%E8%BF%9B%E8%A1%8C%E6%8E%92%E5%BA%8F.%201%20%23include%3Ciostream%3E%202%20using%20namespace,%3C%3C%20endl%3B%208%20return%200%3B%209%20%7D.%20%E8%BF%90%E8%A1%8C%E7%BB%93%E6%9E%9C%EF%BC%9A.
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int N=1e5+10;
typedef pair<int,int> PII;
int n;
vector<PII> s;
/*PII s[N];*/
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
PII t;
int a,b;
cin>>a>>b;
t={a,b};
s.push_back(t);
}
sort(s.begin(),s.end());
int ans=1,R=s[0].second;
for(int i=1;i<n;i++)
{
if(s[i].first<=R)R=min(R,s[i].second);
else
{
ans++;
R=s[i].second;
}
}
cout<<ans<<endl;
}