OpenJudge

4:区间覆盖

总时间限制:
1000ms
内存限制:
65536kB
描述

给定数轴上一个长度为m的闭区间[A, B],再给出N条线段[ai, bi],

求最少使用多少条线段可以将闭区间m完全覆盖。

输入
第1行包含3个整数A,B,N(0 < A < B <= 1E7,0 < N <= 1E5)
第2~N+1行,每行2个整数,表示ai,bi(0 <= ai,bi <= 1E3,i=1...n),空格隔开
输出
一个整数,表示最少需要的线段条数;若不能完成覆盖,输出-1
样例输入
#1:
1 20 7
1 10
2 11
3 12
4 13
5 14
12 19
16 20

#2:
1 10 6
1 5
2 6
3 4
4 7
8 10
2 3
样例输出
#1:
4

#2:
-1
全局题号
14623
添加于
2017-04-15
提交次数
52
尝试人数
18
通过人数
16