贪心
- 按每个区间的右端点排序
- 从第一个区间开始(最左端),如果下一个区间的左端点大于此区间的右端点,则订单数加1,并且将下一个区间更新为此区间。
- 如果下一个区间的左端点小于此区间的右端点,则忽略下一个区间,继续判断下下一个区间。
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 5e5 + 10;
struct Range
{
int l;
int r;
}range[N];
bool operator < (const Range &x,const Range &y)
{
return x.r < y.r;
}
int main()
{
int n;
int l,r;
cin>>n;
for(int i = 0;i < n;i ++)
{
cin>>l>>r;
range[i] = {l,r};
}
sort(range,range + n);
int ans = 0,ed = -2e9;
for(int i = 0;i < n;i ++)
{
if(range[i].l > ed)
{
ans++;
ed = range[i].r;
}
}
cout<<ans<<endl;
return 0;
}
参考 Acwing 908 最大不相交区间数量。