AcWing 422. 校门外的树
原题链接
简单
作者:
Dybala
,
2021-01-30 22:04:21
,
所有人可见
,
阅读 268
C++ 代码,使用pair和vector
#include<bits/stdc++.h>
using namespace std;
bool cmp(pair<int,int>a,pair<int,int>b){
return a.first<b.first;
}
int main(){
int n,m;
cin>>n>>m;
vector<pair<int,int> >road;
for(int i=0;i<m;i++){
int start,end;
cin>>start>>end;
pair<int,int>res(start,end);
road.push_back(res);
}
sort(road.begin(),road.end());//排序
int sum=n+1;
pair<int,int>now=road[0];
for(int i=1;i<m;i++) {
if(road[i].first<=now.second){//几个条件判断,决定是否合并区间
if(road[i].second<now.second)continue;
now.second=road[i].second;
}else{
sum=sum-(now.second-now.first+1);
now=road[i];
}
}
sum=sum-(now.second-now.first+1);//补上最后一次运算
cout<<sum<<endl;
return 0;
}