题目描述
给定 N 个闭区间 [ai,bi] 以及一个线段区间 [s,t],请你选择尽量少的区间,将指定线段区间完全覆盖。
输出最少区间数,如果无法完全覆盖则输出 −1。
输入格式
第一行包含两个整数 s 和 t,表示给定线段区间的两个端点。
第二行包含整数 N,表示给定区间数。
接下来 N 行,每行包含两个整数 ai,bi,表示一个区间的两个端点。
输出格式
输出一个整数,表示所需最少区间数。
如果无解,则输出 −1。
数据范围
1≤N≤105,
−109≤ai≤bi≤109,
−109≤s≤t≤109
样例
输入样例:
1 5
3
-1 3
2 4
3 5
输出样例:
2
问题1
- 为什么是_ r < st 而不是 r <= st_ 来终止循环确认无解?
开始我以为的是 如果更新1次结果后,发现起点未变,那么之后的的更新后陷入循环之中肯定
无解,所以可以直接终止循判题目无解,但问题在于 r < st 能解决目标区间为一个点的特殊情况,
而r <= st不能,并且即使陷入重复更新的循环之中,也会通过success判定最终结果是否成立(这也
是第二个问题为什么要有success的原因之一),所以只能 用 r < st来判断可以终止循环确认无解
问题2
- 为什么有了r < st , res = -1,还需要success 来判断是否有解?
因为r < st 只是无解的一种情况,那就是目标线段的起始无法覆盖,所以可以直接确认无解终止循
环;而success则是为了解决只覆盖一部分而未覆盖全部的这一种情况下的无解
问题3
- 为什么i = j-1,而不是 i= j ?来更新i?
。。经过调试发现:更新r后,j++,所以你懂的(bushi),j-1是更新r时已经遍历过的区间,j 是下一个
还未遍历要遍历的区间。故i= j-1;
代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
struct Range{
int l,r;
bool operator< (const Range &w)const
{
return l<w.l;
}
}range[N];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int st,ed;
cin>>st>>ed;
int n;
cin>>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,r = -2e9;
while(j<n && range[j].l <= st){
r = max(r,range[i].r);
j++;
}
if(r < st){
res = -1;
break;
}
res++;
if(r >= ed){
success = true;
break;
}
st = r;
i = j;
}
if(!success) res = -1;
cout<<res;
return 0;
}