AcWing 907. 区间覆盖——注意细节
原题链接
简单
作者:
会飞的泡泡
,
2021-03-21 19:15:24
,
所有人可见
,
阅读 382
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=1e5+10;
struct dian{
int x,y;
bool operator <(const dian t)const{
return x<t.x;
}
}a[maxn];
int main(){
int st,ed;
int n;
cin>>st>>ed>>n;
for(int i=0; i<n; i++){
cin>>a[i].x>>a[i].y;
}
sort(a,a+n);
int ans=0;
bool success = false;
for(int i=0; i<n; i++){
int j=i;
int r=-2e9;
while(j<n&&a[j].x<=st){
r=max(r,a[j].y);
j++;
}
if(r<st){
ans=-1;
break;
}
cout<<st<<' '<<r<<" "<<endl;
ans++;
if(r>=ed){
success = true;
break;
}
st=r;
i=j-1;
}
if (!success) ans = -1;
printf("%d\n", ans);
return 0;
}