区间合并【简单贪心】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;}
才会看到属于自己的那一片晴朗的天空。
