AcWing 907. 区间覆盖
原题链接
简单
作者:
minux
,
2020-05-05 00:21:46
,
所有人可见
,
阅读 599
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
struct Range{
int l, r;
bool operator< (const Range& o) const{
return l<o.l;
}
}range[N];
int n;
int S, E;
int main(){
cin>>S>>E;
cin>>n;
int a, b;
for(int i=0; i<n; ++i){
cin>>a>>b;
range[i]={a, b};
}
sort(range, range+n);
int res=0;
int r=-2e9;
for(int i=0; i<n;){
int j=i;
// 找到区间的左端点在S的左侧并且右端点最远的区间
while(j<n&&range[j].l<=S){r=max(r, range[j].r); ++j;}
if(r<S) {cout<<-1<<endl; return 0;} // 如果右端点无法覆盖起点返回-1
if(j==i){cout<<-1<<endl; return 0;} // 如果j未更新说明区间之间存在缝隙, 返回-1
++res;
if(r>=E){cout<<res<<endl;return 0;} // 如果已经覆盖区间, 直接输出使用区间的数量
S=r; // 更新区间起点
i=j; // 更新开始循环区间的编号
}
if(r<E) cout<<-1<<endl;
return 0;
}