算法介绍
首先想想脑海中有这样一幅图景:
0.按照区间的右端点从小到大排好序;
1.Start
:取区间的最右侧的边界点(贪);(开始循环)
2.检查下一个区间是否包含这个点
2.1 若包含 则永远不再考虑这个区间(删除此区间)跳到2.
2.2 若不包含 则 LOOP Start
跳到Start处
我们在一个区间选好一个点后,检查下个区间是否可以被这个点pass掉,如果可以那就不再考虑这个区间了,因为已经有一个点了;如果不能则会是下面这种情况:
那我们就继续在第二条线段的右端点上点一个点,这个点肯定比当前点的点更靠右,因为一开始我们就按照右端点排好序了,再拿着这个点往后去判断
代码
#include<iostream>
using namespace std;
#include<algorithm>
#include<vector>
#include<utility>
bool cmp(pair<int,int> x,pair<int,int> y){
return x.second<y.second;
}
int main(void){
int N,fore,rear;
cin>>N;
vector<pair<int,int> > v;
while(N--){
cin>>fore>>rear;
v.emplace_back(make_pair(fore,rear));
}
sort(v.begin(),v.end(),cmp);
int cns=0,dot=-0x3f3f3f3f;//cns表示需要点的数量,dot代表当前或者之前选的区间的右端点
for(auto x:v){
if(x.first>dot) dot=x.second,cns++;//如果当前区间不含有dot,那么更新dot为当前区间的右端点并cns++
}
cout<<cns;
}