分数: 400 分
问题陈述
高桥负责管理他办公室的会议室。今天, N 会议已安排,所有会议必须分配到某个会议室。
的 树的 N 会议编号自 1 to N。会议 i (1 \leq i \leq N) 开始时间 S_i 并于时间结束 E_i。半开期间每次会议占用一个会议室 [S_i, E_i).
两次会议 i, j 被分配到同一个会议室,间隔 [S_i, E_i) 和 [S_j, E_j) 不得重叠。特别是,如果一个会议的结束时间与另一个会议的开始时间一致,则可以在同一会议室连续举行。
办公室有足够数量的会议室,但高桥希望容纳所有会议室 N 会议使用尽可能少的会议室。
将每个会议精确分配到一个会议室,这样就不会出现任何会议室包含时间间隔重叠的会议。找出所需的最少会议室数量。
约束
- 1 \leq N \leq 2 \times 10^5
- 0 \leq S_i < E_i \leq 10^9
- 所有输入值均为整数。
- 可能有多个会议具有相同的开始时间和结束时间。
输入
N S_1 E_1 S_2 E_2 \vdots S_N E_N
- 第一行包含一个整数 N,代表会议次数。
- 从第 2 行到 (N + 1)第行,给出了每次会议的开始时间和结束时间。的 (1 + i)第行(1 \leq i \leq N) 包含开始时间 S_i 和结束时间 会议 E_i 会议的 i,用空格分隔。
输出
在一行中打印分配所有会议室所需的最少会议室数 N 会议。
示例输入 1
3 1 4 2 6 4 7
示例输出 1
2
示例输入 2
4 1 5 2 6 3 7 4 8
示例输出 2
4
示例输入 3
10 0 5 1 3 2 8 3 6 5 10 6 9 7 12 8 11 9 14 1 4
示例输出 3
4
示例输入 4
15 6 14 7 11 8 12 9 13 10 15 0 3 1 4 3 7 14 20 15 18 16 22 20 25 11 16 4 6 18 24
示例输出 4
5
示例输入 5
1 0 1000000000
示例输出 5
1