9024: 区间覆盖
[Creator : ]
Description
给定 $N$ 个闭区间 $[a_i,b_i]$ 以及一个线段区间 $[s,t]$,请你选择尽量少的区间,将指定线段区间完全覆盖。
输出最少区间数,如果无法完全覆盖则输出 $−1$。
输出最少区间数,如果无法完全覆盖则输出 $−1$。
Input
第一行包含两个整数 $s, t$,表示给定线段区间的两个端点。
第二行包含整数 $N$,表示给定区间数。
接下来 $N$ 行,每行包含两个整数 $a_i,b_i$,表示一个区间的两个端点。
第二行包含整数 $N$,表示给定区间数。
接下来 $N$ 行,每行包含两个整数 $a_i,b_i$,表示一个区间的两个端点。
Output
输出一个整数,表示所需最少区间数。
如果无解,则输出 $−1$。
如果无解,则输出 $−1$。
Constraints
$1≤N≤2 \times 10^5$
$−10^9≤a_i≤b_i≤10^9$
$−10^9≤s≤t≤10^9$
$−10^9≤a_i≤b_i≤10^9$
$−10^9≤s≤t≤10^9$
Sample 1 Input
1 5
3
-1 3
2 4
3 5
Sample 1 Output
2
Sample 2 Input
-7 5
5
-8 -4
-4 -2
-2 1
0 3
3 6
Sample 2 Output
5