AcWing 422. 校门外的树
原题链接
简单
作者:
alxmn
,
2021-01-16 18:24:58
,
所有人可见
,
阅读 347
题目描述:区间合并求数目
算法一:暴力
#include<stdio.h>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
const int N=10010;
bool p[N];
int main(void){
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++){
int a,b;
cin>>a>>b;
for(int j=a;j<=b;j++)
p[j]=true;
}
int res=0;
for(int i=0;i<=n;i++){
if(!p[i]){
res++;
}
}
cout<<res;
}
时间复杂度0(n*m);
算法二:区间合并
#include<stdio.h>
#include<algorithm>
#include<iostream>
using namespace std;
typedef pair<int,int> pp;
const int N =110;
pp a[N];
int main(void){
int l,m;
cin>>l>>m;
for(int i=0;i<m;i++){
cin>>a[i].first>>a[i].second;
}
sort(a,a+m);int sum=0;
int st=a[0].first,ed=a[0].second;
for(int i=1;i<m;i++){
if(a[i].first>ed){
sum+=ed-st+1;
st=a[i].first;ed=a[i].second;
}
else{
ed=max(ed,a[i].second);
}
}
sum+=ed-st+1;
int res=l+1-sum;
cout<<res<<endl;
}
时间复杂度由排序决定o(m*log2m)