题目描述
给定 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
(贪心)
y总想用一套固定的《ans<=cnt,ans>=cnt->ans==cnt》来证明,我并没有听懂
关于这题我的思路是:每一步都往远了够,我们想象一下一个人在高空中的木板 上走,这些木板都是固定的,他想竟可能的走的远,那么就需要从自己够得到的地方尽可能的往远了够,最终达到目的,任何一个其他的方案都会比上述方案短
步骤:
1.将所有区间按照左端点从小到大排序
2.从前往后枚举每一个区间,在所有不超过st的区间中,选出那个右端点最大的区间,并且按照这个区间来更新st值
时间复杂度
参考文献
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int n;
int st,ed;
struct range
{
int l,r;
bool operator < (const range &W)const//重载运算符
{
return this->l<W.l;
}
}ranges[N];
int main()
{
cin>>st>>ed>>n;//读入数据
for(int i=0;i<n;i++)
{
int a,b;
cin>>a>>b;
ranges[i]={a,b};
}
sort(ranges,ranges+n);//排序
int res=0;
bool ok;
for(int i=0;i<n;i++)
{
int j=i,r=-2e9;
while(j<n&&ranges[j].l<=st)
{
r=max(r,ranges[j].r);
j++;
}
if(r<st)
{
res=-1;//没有接班人,中间必有空隙,直接remake
break;
}
res++;
if(r>=ed)
{
ok=true;//已经结束啦!
break;
}
st=r;//已经覆盖掉的删除
i=j-1;//这是由于之前选出最大右端点时更新过j,所以这里同步更新一下
}
if(!ok)res=-1;
cout<<res<<endl;
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla