2026 CSP-S 模拟卷（一）T1 任务排程

题目背景与题意

小 Z 给自己列了一份训练计划，共有 $n$ 个任务。第 $i$ 个任务需要连续 $t_i$ 分钟才能完成，必须在第 $d_i$ 分钟结束之前或正好结束（即完成时刻不超过 $d_i$）。所有任务从第 0 分钟开始，同一时刻只能做一个任务，任务之间不能重叠、不能中断，也不必按输入顺序完成。小 Z 想知道：在不违反任何截止时间的前提下，最多能完成多少个任务？如果一个任务做不完，他可以选择直接放弃它。

注意：被放弃的任务完全不影响其他任务，也就是说，你只需要挑出一个任务集合，并给它们安排一个执行顺序，使得按这个顺序依次连续执行时，每个任务都在自己的截止时间前完成。你要求的是这个集合的最大可能大小。

输入格式

第一行一个整数 $n$，表示任务数。

接下来 $n$ 行，每行两个整数 $d_i, t_i$，依次表示截止时间与所需时长。

输出格式

一行一个整数，表示最多能完成的任务数。

样例输入

4
5 3
8 4
3 5
20 2

样例输出

3

样例解释

四个任务分别是：截止 5 分钟、耗时 3 分钟；截止 8 分钟、耗时 4 分钟；截止 3 分钟、耗时 5 分钟；截止 20 分钟、耗时 2 分钟。

第三个任务耗时 5 分钟而截止时间只有 3 分钟，单做它也来不及，必须放弃。剩下三个任务按「截止 5 分钟的先做、再截止 8 分钟、最后截止 20 分钟」的顺序执行：第 3 分钟完成第一个，第 7 分钟完成第二个，第 9 分钟完成第三个，全部满足截止要求，共 3 个。所以答案是 3。

数据范围与子任务

对全部数据：$1 \le n \le 2\times 10^5$，$1 \le d_i, t_i \le 10^9$。

子任务采用捆绑测试：子任务内部的测试点必须全部通过才能拿到该子任务的全部分值，否则该子任务得 0 分。

时间限制 1 秒，空间限制 512 MB。