AcWing 907. 区间覆盖
原题链接
简单
作者:
术
,
2021-03-08 13:47:26
,
所有人可见
,
阅读 252
#include <iostream>
#include <algorithm>
using namespace std;
const int N=100005;
struct Node
{
int l,r;
bool operator<(const Node &b)const
{
return l<b.l;
}
} node[N];
int main()
{
int n;
int start,ed;
cin>>start>>ed;
cin>>n;
for(int i=0; i<n; i++)
{
int l,r;
cin>>l>>r;
node[i]= {l,r};
}
sort(node,node+n);
int res=0;
bool success=false;
for(int i=0; i<n; i++)
{
int j=i;
int max_r=-2e9;
while(j<n&&node[j].l<=start) //由于是按左端点排序,所以可以搜出符合要求的最大右端点
{
max_r=max(max_r,node[j].r);
j++;
}
// cout<<"st:"<<start<<endl;
if(max_r<start)//会有空隙区间 不判断会超时
{
res=-1;
break;
}
res++;
if(max_r>=ed)
{
success=true;
break;
}
i=j-1;//还原
start=max_r;
}
if(!success)
cout<<-1<<endl;
else
cout<<res;
//cout << "Hello world!" << endl;
return 0;
}