题目描述

现有单线程处理器与 $N$ 个任务，每个任务 $i$ 有两个参数：

• $t_i$：任务所需连续处理时长，不可中断；
• $d_i$：任务截止时间（从时刻 0 开始计时）。

执行规则：

1. 任务一旦开始不能中断，完成后可立刻执行下一个；
2. 若任务结束时刻 $\le d_i$，则该任务按时完成。

你可以任意安排任务执行顺序，求最多能按时完成的任务数量。

输入格式

第一行整数 $N$，代表任务总数。 接下来 $N$ 行，每行两个整数 $t_i, d_i$。

输出格式

输出一个整数：最多可按时完成的任务数量。

算法思路（经典贪心+大根堆）

1. 将所有任务按截止时间 $d_i$ 升序排序；
2. 维护总耗时 sum_time，以及一个存储已选任务时长的大根堆；
3. 遍历每个任务 $(t,d)$：
   • 把当前任务加入堆，sum_time += t；
   • 若 sum_time > d：说明当前这批任务无法全部按时完成，删除耗时最长的任务（堆顶），sum_time -= 堆顶值；
4. 遍历结束后，堆内元素个数即为最多可完成任务数。

原理：优先选截止早的任务；超时则剔除当前最耗时任务，用更少总时长保留更多任务。

样例输入 1

3
3 5
2 4
1 3

样例输出 1

2

解释

排序后任务：$(1,3),(2,4),(3,5)$

1. 加入(1,3)：sum=1 ≤3，堆[1]
2. 加入(2,4)：sum=3 ≤4，堆[2,1]
3. 加入(3,5)：sum=6 >5，弹出最大3，sum=3，堆[2,1] 堆大小为2，答案2。

样例输入 2

4
1 2
1 3
2 4
3 7

样例输出 2

4

解释

按截止排序后依次加入，总耗时1,2,4,7均不超过对应截止，全部保留，堆大小4。

样例输入 3

5
4 5
3 6
2 3
5 10
1 2

样例输出 3

3

解释

排序后：(1,2),(2,3),(4,5),(3,6),(5,10)

1. (1,2): sum=1 ≤2，堆[1]
2. (2,3): sum=3 ≤3，堆[2,1]
3. (4,5): sum=7>5，删4，sum=3，堆[2,1]
4. (3,6): sum=6 ≤6，堆[3,1,2]
5. (5,10): sum=11>10，删5，sum=6，堆[3,1,2] 堆长度3，答案3。

数据范围与约束