分数: 625 点
问题陈述
N 苹果落在数轴上。苹果 i 落在坐标处 X_i 时间 T_i.
你想在数轴上放置一些机器人来收集所有 N 苹果。机器人可以放置在任意坐标。
每个机器人从时间开始运行 0 并且可以沿数轴自由移动,速度最多为 1。多个机器人可以同时占据同一坐标。每个机器人都可以收集苹果 i 当且仅当它位于坐标处 X_i 时间 T_i.
找出收集所有苹果所需的最少机器人数量。
约束
- 1 \le N \le 3 \times 10^5
- 0 \le T_i \le 3 \times 10^5
- 0 \le X_i \le 3 \times 10^5
- (T_i, X_i) \neq (T_j, X_j) (i \neq j)
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N T_1 X_1 T_2 X_2 \vdots T_N X_N
输出
输出答案。
示例输入 1
4 0 2 1 0 2 1 2 3
示例输出 1
2
所有苹果都可以通过两个机器人通过移动来收集,如下所示:
- 放置机器人 1 位于坐标处 0 和机器人 2 位于坐标处 2.
- 时间 0:机器人 2 收集苹果 1.
- 时间 1:机器人 1 收集苹果 2。使两个机器人快速向正方向移动 1 直到时间 2.
- 时间 2:机器人 1 收集苹果 3 和机器人 2 收集苹果 4.
少于两个机器人不可能收集到所有苹果,因此输出 2.
示例输入 2
5 0 1 0 2 0 3 0 4 0 5
示例输出 2
5
示例输入 3
8 10 4 4 2 7 10 5 3 1 9 0 6 3 8 0 9
示例输出 3
2