AcWing 907. 区间覆盖
//written by 2023/6/7
include[HTML_REMOVED]
include[HTML_REMOVED]
using namespace std;
const int N = 100010;
struct Range{
int l,r;
bool operator < (const Range &W)const{
return l < W.l;
}
}range[N];
int main(){
int n,s,t;
cin>>s>>t>>n;
for(int i = 0;i < n;i){
cin>>range[i].l>>range[i].r;
}
sort(range,range+n);
int res = 0;
//在所有区间左端点大于这个线段左端点的区间中找这些区间
//哪个右端点最大(能覆盖的长度更大),下一轮则与上一轮
//右端点最大的点进行比较
bool success = false;
for(int i = 0;i < n;i){
int j = i;int start = -2e9;
while(j < n && range[j].l <= s){
start = max(start,range[j].r);
j;
}
res;
if(start < s){
res = -1;
break;
}
if(start >= t){
success = true;
break;
}
s = start;
i = j-1;
}
// 1 5
// 2
// -1 2
// 2 4
//增加success状态是为了避免上述用例情况,每次start都>s,但是start<t,这种情况也无法覆盖
if (!success) res = -1;
printf(“%d\n”, res);
return 0;
}
1、为什么要用sucess来标注是否覆盖了呢
因为不覆盖有两种情况,循环中只判断了第一种
下图为两种情况
http://www.wusi.fun/media/topic_photo/%E5%BE%AE%E4%BF%A1%E6%88%AA%E5%9B%BE_20230607232424.png