#O1083. 区间覆盖
区间覆盖
题目描述
给出 个闭区间 ,要用最少的区间覆盖整个线段 。输出最少需要的区间数,若无法覆盖输出 -1。
输入格式
第一行一个整数 。
接下来 行,每行两个整数 。
输出格式
一行一个整数,表示最少区间数,或 -1。
样例 #1
样例输入 #1
5
1 3
2 5
4 6
5 8
7 9
样例输出 #1
-1
数据规模与约定
| 数据范围 | 说明 |
|---|---|
| 区间个数 | |
| 区间端点 |
- 按左端点排序后贪心:每次在能接上的区间中选择右端点最远的。
- 样例中的区间只能覆盖到 ,达不到 。