鸿 网 互 联 www.68idc.cn

当前位置 : 服务器租用 > 编程语言开发 > java > >

区间合并【简单贪心】acwing803

来源:互联网 作者:佚名 时间:2022-07-19 11:16
区间合并【简单贪心】acwing803 将所有区间进行排序,按照左端点从小到大、右端点从小到大的优先级排序,然后遍历判断每一个区间是否能和前面的区间合并即可。 ac代码: #includebi


区间合并【简单贪心】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;
}


上一篇:题目:CSP 201612-3 权限查询
下一篇:没有了
网友评论
<