区间合并【简单贪心】acwing803

区间合并【简单贪心】acwing803

将所有区间进行排序，按照左端点从小到大、右端点从小到大的优先级排序，然后遍历判断每一个区间是否能和前面的区间合并即可。

ac代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int n,l,r;
pii v[100005];
bool note[100005];
bool cmp(pii a,pii b){
if(a.first < b.first)
return true;
else if(a.first > b.first)
return false;
return a.second < b.second;
}
signed main(){
IOS
cin>>n;
for(int i = 1;i <= n;++i)
cin>>v[i].first>>v[i].second;
sort(v + 1,v + n + 1,cmp);
int mn = v[1].second;note[1] = true;
for(int i = 2;i <= n;++i)
if(v[i].first <= mn)
mn = max(v[i].second,mn);
else
mn = v[i].second,note[i] = true;
int ans = 0;
for(int i = 1;i <= n;++i)
ans += note[i];
cout<<ans;
return 0;
}