分数: 400 分
问题陈述
Takahashi 负责管理其公司的会议室预订。公司仅有 1 会议室,最多 1 会议可以在任何给定时间举行。
有一天, N 会议预订请求已到达。的 i第 次会议开始时间 L_i 并于时间结束 R_i (L_i < R_i)。由于只有一间会议室,时间重叠的会议无法同时举行。
在这里,两次会议 i 和 j 如果间隔被称为“重叠” (L_i, R_i) 和 (L_j, R_j) 有一个共同的部分,那就是,如果 L_i < R_j 和 L_j < R_i 两者都成立。如果一个会议的结束时间与另一会议的开始时间一致(例如, R_i = L_j),它们被认为是不重叠的并且可以连续持有。
高桥希望安排尽可能多的会议。找到可以选择的最大会议数,使得其中没有两个会议重叠。
约束
- 1 \leq N \leq 2 \times 10^5
- 0 \leq L_i < R_i \leq 10^9
- 所有输入值均为整数。
输入
N L_1 R_1 L_2 R_2 : L_N R_N
- 第一行包含 N,会议预订请求的数量。
- 从第 2 行到 (N + 1)第行,开始时间 L_i 和结束时间 每次会议的 R_i 均以空格分隔。
- 的 (1 + i)-第行包含开始时间 L_i 和结束时间 每次会议的 R_i 的 i第次会议。
输出
在一行中打印可以选择的最大会议数,确保其中没有两个会议重叠。
示例输入 1
5 1 5 3 8 1 3 5 8 2 6
示例输出 1
2
示例输入 2
8 1 4 3 6 2 4 5 9 5 7 7 9 9 10 1 2
示例输出 2
5
示例输入 3
12 0 100 50 150 100 200 200 500 150 300 300 600 500 700 600 800 700 800 750 900 1000 1000000000 999999999 1000000000
示例输出 3
6