该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

2026模拟卷（一）T2 单机排程

题目背景

小 Z 的实验台上只有一台加工设备，同一时刻只能加工一个零件。一批任务已经排好队等待加工，每个任务都有一个加工时长和一个交付期限。

题目描述

有 $n$ 个任务，编号为 $1$ 到 $n$。第 $i$ 个任务的加工时长为 $t_i$（单位：分钟），交付期限为 $d_i$（单位：分钟）。

所有任务都在时刻 $0$ 就绪。设备从时刻 $0$ 开始工作，并且任何时刻最多加工一个任务。一个任务一旦开始加工就必须连续做完，中间不能被打断，也不能被拆成几段。如果你决定加工某些任务，就必须把它们排成一个加工顺序；在这个顺序下，第 $i$ 个任务的实际完工时刻等于它前面所有已加工任务的加工时长之和再加上 $t_i$。

一个任务被「按时完成」，当且仅当它的实际完工时刻不超过它的交付期限 $d_i$。

请你从这 $n$ 个任务中选出尽可能多的任务并排好顺序，使得被选中的任务全部按时完成。输出这个最大数量。

输入格式

第一行一个整数 $n$。 接下来 $n$ 行，每行两个整数 $t_i$ 与 $d_i$，用一个空格隔开。

输出格式

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

样例输入

5
3 5
2 4
1 2
4 9
5 12

样例输出

4

样例解释

五个任务按交付期限从小到大排是：任务 3 $(t=1,\ d=2)$、任务 2 $(t=2,\ d=4)$、任务 1 $(t=3,\ d=5)$、任务 4 $(t=4,\ d=9)$、任务 5 $(t=5,\ d=12)$。

先看能否做满 5 个：全部加工的总时长是 $3+2+1+4+5 = 15$，不论怎么排队，最后一个任务的完工时刻都不小于 15，而所有期限里最大也只有 12，所以 5 个不可能。

再看 4 个。选择任务 2、3、4、5，按「任务 3、任务 2、任务 4、任务 5」的顺序加工：

四个任务全部按时完成，总时长为 $1+2+4+5 = 12$。所以答案是 4。

顺带说明为什么不能选任务 1：任务 1 的时长是 3、期限只有 5。若同时选中任务 1、2、3，总时长已达 $1+2+3 = 6 > 5$，其中至少有一个超期，所以任务 1 与任务 2、3 无法共存。

数据范围

对于 $100\%$ 的数据，$1 \le n \le 2\times10^5$，$1 \le t_i \le 10^9$，$1 \le d_i \le 10^9$。