Information
- ID
- 250
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 5
- Tags
- # Submissions
- 11
- Accepted
- 4
- Uploaded By
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef pair<int,int> PII;
#define l first
#define r second
PII q[N];
int main()
{
int st,ed;
cin>>st>>ed;
int n;
cin>>n;
for(int i=0;i<n;i++)
{
int l,r;
cin>>l>>r;
q[i]={l,r};
}
sort(q,q+n);
int res=0;
bool su=false;
for(int i=0;i<n;i++)
{
int r=-2e9;
int j=i;
while(j<n&&q[j].l<=st)
{
r=max(r,q[j].r);
j++;
}
j--; //走到小于等于起点的地方
if(r<st) break; //最长的右端点也小于起点
res++;
if(r>=ed) //已经完全覆盖
{
su=true;
break;
}
st=r; //更新当前选择点以后可以覆盖到的最远的点
i=j;
}
if(su) cout<<res;
else cout<<-1;
return 0;
}