分析
这显然是一个 贪心问题,多积累一些贪心问题吧,培养点感觉~~✊
这题的贪心算法是:
先对区间的左端点从小到大进行排序,然后不断地从前往后把能碰到一点的区间都合并上。
那假如按右端点从小到大排序会怎样呢?
如上图所示按照右端点从小到大排序的话,你再从前往后的合并区间显然就错了,因为这三个区间显然应该是可以合并成一个区间的,可是按右端点排序之后就变成1为一个区间,2,3为一个区间了。(那你按右端点从小到大排序时,从后往前合并区间对吗??)
代码及详解
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
#define fi first
#define se second
typedef pair<int,int> PII;
void merge(vector<PII> &seg){
vector<PII> res;
int st=-2e9,ed=-2e9;
for(int i=0;i<seg.size();i++){
if(ed<seg[i].fi){
if(st!=-2e9) res.push_back({st,ed});//由于ed=-2e9定小于任意区间的左端点,一开始便会把st,ed更新为seg第一个区间的值
st=seg[i].fi;
ed=seg[i].se;
}else{
ed=max(ed,seg[i].se);
}
}
if(st!=-2e9) res.push_back({st,ed});//把最后一个区间合并进来 1).当是ed<seg[i].f结束时,此时新的这一段区间
//seg[i].fi,seg[i].se显然没有被加入到res中;2).当是else结束的时候,此时区间根本还没加入到res中就退出了;因此只要seg不是
//空的,不管怎样最后还剩一段区间没有合并
seg=res;
}
int main(){
int n;
scanf("%d",&n);
vector<PII> seg;
while(n--){
int l,r;
scanf("%d%d",&l,&r);
seg.push_back({l,r});
}
sort(seg.begin(),seg.end());//默认以pair的第一关键字排序
merge(seg);
cout<<seg.size();
return 0;
}