AcWing 908. 最大不相交区间数量
原题链接
简单
作者:
月下邂逅
,
2024-04-24 14:12:54
,
所有人可见
,
阅读 1
C++ 代码
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef pair<int,int> pii;
vector<pii> interval;
int main()
{
int n,l,r,res=0;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d%d",&l,&r);
interval.push_back({l,r});
}
sort(interval.begin(),interval.end());//左端点排序
int end=interval[0].second;
for(int i=1;i<interval.size();i++)
{
if(end>=interval[i].first)//如果相交则取右端点小的,因为左端点从小到大排序,
//所以这里相当于是最后一个区间和当前区间取右端点最小值(好处是)并且不会影响前面的选择
{
end=min(end,interval[i].second);
}
else//如果和当前选中所有区间不想交,则区间数量++,更新end
{
res++;
end=interval[i].second;//interval[i].second>=interval[i].first>end
}
}
res++;//加上最后一个区间
printf("%d",res);
return 0;
}