信阳市工程建设信息网站,软文世界,扬中潘杰,服装营销方式和手段给定 NN 个闭区间 [ai,bi][ai,bi] 以及一个线段区间 [s,t][s,t]#xff0c;请你选择尽量少的区间#xff0c;将指定线段区间完全覆盖。
输出最少区间数#xff0c;如果无法完全覆盖则输出 −1−1。
输入格式
第一行包含两个整数 ss 和 tt#xff0c;表示给定线段区间的两…给定 NN 个闭区间 [ai,bi][ai,bi] 以及一个线段区间 [s,t][s,t]请你选择尽量少的区间将指定线段区间完全覆盖。
输出最少区间数如果无法完全覆盖则输出 −1−1。
输入格式
第一行包含两个整数 ss 和 tt表示给定线段区间的两个端点。
第二行包含整数 NN表示给定区间数。
接下来 NN 行每行包含两个整数 ai,biai,bi表示一个区间的两个端点。
输出格式
输出一个整数表示所需最少区间数。
如果无解则输出 −1−1。
数据范围
1≤N≤1051≤N≤105, −109≤ai≤bi≤109−109≤ai≤bi≤109, −109≤s≤t≤109−109≤s≤t≤109
输入样例
1 5
3
-1 3
2 4
3 5输出样例
2
#includebits/stdc.h
using namespace std;
const int N 100010;
int st,ed;
int n;
struct Range
{int l,r;bool operator (const Range w)const{return lw.l;}}range[N];
int main()
{cinsted;cinn;for(int i0;in;i){int l,r;scanf(%d %d,l,r);range[i]{l,r};}sort(range,rangen);int res0;bool flagfalse;for(int i0;in;i){int ji,r-2e9;while(jn range[j].lst){rmax(r,range[j].r);j;}if(rst){res-1;break;}res;if(red){flagtrue;break;}str;ij-1;}if(!flag) res-1;coutres;return 0;
}
