Job Completion

题目描述

奶牛 Bessie 有 $N$（$1\le N\le 2\cdot 10^5$）个工作供你选择完成。第 $i$ 个工作如果你选择完成，必须在时间 $s_i$ 或之前开始，并且需要 $t_i$ 的时间才能完成（$0\le s_i\le 10^{18}, 1\le t_i\le 10^{18}$）。问你最多能完成多少个工作？时间从 $0$ 开始，一旦你开始一个工作，就必须一直做直到完成，在此期间不能开始其他工作。

输入格式

第一行包含 $T$，表示相互独立的测试用例数量（$1\le T\le 10$）。每个测试用例格式如下。 第一行包含 $N$。 接下来 $N$ 行每行包含两个整数 $s_i$ 和 $t_i$。第 $i+1$ 行给出第 $i$ 个工作的信息。 保证所有测试用例中 $N$ 的总和不超过 $3\cdot 10^5$。

输出格式

对于每个测试用例，输出一行，表示你最多能完成的工作数量。

3
2
1 4
1 2
2
2 3
1 2
3
1 4
2 3
1 2

1
2
2

提示

对于第一个测试用例，你只能完成其中一个工作。完成一个工作后，时间将变为 $2$ 或更晚，因此已经来不及开始另一个工作，因为另一个工作必须在时间 $1$ 或更早开始。 对于第二个测试用例，你可以在时间 $0$ 开始第二个工作并在时间 $2$ 完成，然后在时间 $2$ 开始第一个工作并在时间 $5$ 完成。 SCORING: Inputs 2: 在同一个测试用例中，所有 $t_i$ 都相等。 Inputs 3-4: $N\le 2000$, $s_i, t_i\le 2000$ Inputs 5-8: $N\le 2000$ Inputs 9-16: 无额外限制。 Problem credits: Benjamin Qi

标签: USACO|2024|Gold

来源

USACO|2024|Gold