问题分析
这题和问题 区间选点 几乎是一毛一样
第一步:按右端点排序(为什么不按左端点?左端点排序后如果第一个区间非常长,以至于能触碰到之后的所有区间,那就直接gg了)
第二步:枚举。每次选择一个区间,然后去掉这个区间右端点能够触碰到的所有区间(其实就是判断当前枚举的区间左端点是否小于等于上次被选区间的右端点),由于是按照右端点从小到大排序的,所以每次枚举的区间右端点是尽可能小的,也就尽量不会筛掉后面更多区间,这其实就是一个局部最好的情况。
C++ 代码
用pair来存区间
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int,int> PII;
const int N = 1e5+10;
int n;
PII q[N];
int main(){
cin>>n;
for(int i=0;i<n;i++){
int l,r;
cin>>l>>r;
q[i] = {r,l}; //右端点是第一关键字,用于对右端点排序
}
sort(q,q+n);
int res = 0, end = -1e9; //被选的区间数、上次被选区间的右端点
for(int i=0;i<n;i++){
int r = q[i].first, l = q[i].second;
if(l > end)
{
res++;
end = r;
}
}
cout<<res;
return 0;
}
用结构体存区间
时间效率比pair版本好一丢丢
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int n;
struct R{
int l,r;
bool operator < (const R &W){
return r < W.r;
}
}q[N];
int main(){
cin>>n;
for(int i=0;i<n;i++){
int l,r;
cin>>l>>r;
q[i].l = l, q[i].r = r; //右端点是第一关键字,用于对右端点排序
}
sort(q,q+n);
int res = 0, end = -1e9; //被选的区间数、上次被选区间的右端点
for(int i=0;i<n;i++){
if(q[i].l > end)
{
res++;
end = q[i].r;
}
}
cout<<res;
return 0;
}