#O1083. 区间覆盖

区间覆盖

题目描述

给出 nn 个闭区间 [li,ri][l_i,r_i],要用最少的区间覆盖整个线段 [0,109][0,10^9]。输出最少需要的区间数,若无法覆盖输出 -1。

输入格式

第一行一个整数 nn。

接下来 nn 行,每行两个整数 li,ril_i,r_i。

输出格式

一行一个整数,表示最少区间数,或 -1。

样例 #1

样例输入 #1

5
1 3
2 5
4 6
5 8
7 9

样例输出 #1

-1

数据规模与约定

数据范围 说明
1≤n≤1051 \le n \le 10^5 区间个数
0≤li≤ri≤1090 \le l_i \le r_i \le 10^9 区间端点
  • 按左端点排序后贪心:每次在能接上的区间中选择右端点最远的。
  • 样例中的区间只能覆盖到 99,达不到 10910^9。