最大不相交区间数量
题目 最大不相交区间数量
思路分析
数轴上有一些区间，选取几个区间，要求所选的区间没有重合部分，求最多能选多个区间
发现也是交集问题 和上一题是一模一样的
把上题代码copy一下就能过
但是重新默写一遍
代码实现
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n;
struct Range{
int l,r;
bool operator< (const Range &w)const{
return r<w.r;
}
}ranges[N];
int main()
{
cin>>n;
for(int i=0;i<n;i++)
cin>>ranges[i].l>>ranges[i].r;
sort(ranges,ranges+n);
int res=0;
int ed=-2e9;
for(int i=0;i<n;i++){
if(ranges[i].l>ed){
res++;
ed=ranges[i].r;
}
}
cout<<res;
return 0;
}
💬 评论