AcWing 907. 区间覆盖
给定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
思路:
首先对每个点的左边界进行排序,然后枚举到开头前的点能最远到达的右边界,如果不能覆盖开始说明无解,如果可以覆盖到终点,说明覆盖完成,若不能完全覆盖,则更新开头为最远右边界覆盖。
主要思想
贪心
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
struct Range
{
int l,r;
bool operator<(const Range &W)
{
return l<W.l;
}
} range[N];
int main(void)
{
int a,b;
cin>>a>>b;
int n;
cin>>n;
for(int i=0;i<n;i++)
cin>>range[i].l>>range[i].r;
sort(range,range+n);
int rg=-2e9,cnt=0;
bool flag=false;
int z=0;
for(int i=0;i<n;i++)
{
int j=i;rg=-2e9;
while(j<n&&range[j].l<=a)
{
rg=max(rg,range[j].r);
j++;
}
if(rg<a)
{
flag=false;
break;
}
cnt++;
if(rg>=b)
{
flag=true;
break;
}
a=rg;
i=j-1;
}
if(flag)
cout<<cnt;
else
puts("-1");
}