接住所有苹果AI (CI翻译)
Problem Statement
题目描述
AI (CI翻译)$N$ apples fall on a number line. Apple $i$ falls at coordinate $X_i$ at time $T_i$.
数轴上有 $N$ 个苹果。苹果 $i$ 在时刻 $T_i$ 落在坐标 $X_i$ 处。AI (CI翻译)
You want to place some robots on the number line to collect all $N$ apples. The robots can be placed at any coordinates.
你想在数轴上放置一些机器人来收集全部 $N$ 个苹果。机器人可以放置在任意坐标处。AI (CI翻译)
Each robot starts operating from time $0$ and can move freely along the number line at a speed of at most $1$. Multiple robots may occupy the same coordinate at the same time. Each robot can collect apple $i$ if and only if it is at coordinate $X_i$ at time $T_i$.
每个机器人从时刻 $0$ 开始运行，可以沿数轴自由移动，速度不超过 $1$。多个机器人可以在同一时刻位于同一坐标处。当且仅当某个机器人在时刻 $T_i$ 位于坐标 $X_i$ 处时，它才能收集苹果 $i$。AI (CI翻译)
Find the minimum number of robots needed to collect all apples.
求收集所有苹果所需的最少机器人数量。AI (CI翻译)
Constraints
约束条件
AI (CI翻译)$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)$- All input values are integers.
$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)$- 所有输入值均为整数。
Input
输入格式
AI (CI翻译)The input is given from Standard Input in the following format:
输入从标准输入按以下格式给出：AI (CI翻译)
N
T_1 X_1
T_2 X_2
\vdots
T_N X_NN
T_1 X_1
T_2 X_2
\vdots
T_N X_NOutput
输出格式
AI (CI翻译)Output the answer.
输出答案。AI (CI翻译)
样例
4
0 2
1 0
2 1
2 3
2
5
0 1
0 2
0 3
0 4
0 5
5
8
10 4
4 2
7 10
5 3
1 9
0 6
3 8
0 9
2
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。