分数: 400 分
问题陈述
高桥正在为一条长走廊制定安全计划,其中包括 N 部分(来自部分 1 至部分 N) 排列成一条直线。他必须确保所有部分都受到保安保护。
高桥已聚集 M 警卫候选人。各后卫候选人 i (1 \leq i \leq M) 可以覆盖节中的连续范围 L_i 至部分 R_i。也就是说,如果后卫候选人 i 已分配,部分 L_i, L_i + 1, \ldots, R_i 全部被覆盖。
高桥想要全部 N 要涵盖的部分。具体来说,他想选择一些 M 守卫候选者,使得所选守卫覆盖的部分的并集等于 \{1, 2, \ldots, N\}。每个后卫候选人可以选择或者不选择;同一候选人不能被多次选中。
找到需要分配的最少警卫人数。如果无论如何选择防护都无法覆盖所有部分,则输出 -1.
约束
- 1 \leq N \leq 10^9
- 1 \leq M \leq 2 \times 10^5
- 1 \leq L_i \leq R_i \leq N (1 \leq i \leq M)
- 所有输入均为整数
输入
N M L_1 R_1 L_2 R_2 \vdots L_M R_M
- 第一行包含一个整数 N 表示节数和整数 M 代表警卫候选人的数量,以空格分隔。
- 从第 2 行到 (M + 1)第行,给出了每个守卫候选者可以覆盖的部分范围。
- 的 树的 (i + 1)- 第行 (1 \leq i \leq M) 包含左端点 L_i 和右端点 守护候补区间的 R_i 保护候选人的部分范围 i 可以覆盖,用空格隔开。
输出
在一行中输出覆盖所有部分所需的最少警卫数量。如果不可能,则输出 -1.
示例输入 1
10 3 1 5 3 7 6 10
示例输出 1
2
示例输入 2
15 4 1 3 5 8 10 12 13 15
示例输出 2
-1
示例输入 3
1000000000 5 1 300000000 200000000 500000000 400000000 700000000 600000000 900000000 800000000 1000000000
示例输出 3
5