区间合并【简单贪心】acwing803

区间合并【简单贪心】acwing803

区间合并【简单贪心】acwing803

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

ac代码：

#includeusing namespace std;#define int long long#define pii pair#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<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。