$\huge \color{orange}{成仙之路->}$ $\huge \color{purple}{算法基础课题解}$
思路:
1. 先将所有区间按右端点排序,选择首个区间的右端点
2. 假如当前区间的左端点大于已选定区间的右端点,那么就将当前区间确定为已选定区间
完整代码
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int n;
struct Range
{
int l,r;
bool operator< (const Range &w) const
{
return r<w.r;
}
}range[N];
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
int l,r;
cin>>l>>r;
range[i]={l,r};
}
sort(range,range+n); //按区间的右端点排序
int res=0,ed=-2e9;
for(int i=0;i<n;i++)
if(range[i].l>ed) //当前区间的左端点大于已选定区间的右端点
{
res++; //最多有几个不相交的区间
ed=range[i].r; //选择当前区间的右端点
}
cout<<res<<endl;
return 0;
}