题目描述
不想复述
算法1
完全模板法,基本代码都没有变的
时间复杂度
应该是卡在排序那里了
参考文献
就是课程里面的模板
C++ 代码
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef pair<int,int> PII;
vector<PII> alls;
void merge(vector<PII> & alls){
vector<PII> res;
int st=-1,ed=-1;
sort(alls.begin(),alls.end());
for(auto x:alls){
if(ed<x.first){
if(st!=-1) res.push_back({st,ed});
st=x.first,ed=x.second;
}
else ed=max(ed,x.second);
}
if(ed!=-1) res.push_back({st,ed});
alls=res;
}
int main(){
int L,M;
cin>>L>>M;
while(M--){
int l,r;
cin>>l>>r;
alls.push_back({l,r});
}
merge(alls);
long long sum=0;
for(auto x:alls){
sum+=(x.second-x.first+1);
}
long long res = L+1-sum;
cout<<res;
return 0;
}