/ Vijos / 题库 /

维修任务

维修任务

时间限制:1秒  内存限制:256M


【题目描述】

  一名工人接到 𝑛 个维修任务,其中第 𝑖 个任务需要 𝑡[𝑖] 秒时间,且必须在 𝑑[𝑖] 秒之前完成。同时,修理工人修理完一个任务才能修理下一个任务,不能同时修理多个任务。那么这名工人最多能完成多少个任务?

【输入格式】

  第一行是一个整数 \(n\),接下来 \(n\) 行每行两个整数 \(t_i, d_i\),意义如题目描述。

【输出格式】

  一个整数 \(S\),表示最多可以完成 \(S\) 个任务。

【输入输出样例】

 Input

4
100 200
200 1300
1000 1250
2000 3200

 Output

3

【数据限制】

  对于 \(100\%\) 的数据,\(1≤N≤150,000\),\(T_1 < T_2 <2^{31}-1\)

【来源】

  Mr.he

信息

ID
2788
难度
(无)
分类
贪心 | 数据结构 | 点击显示
标签
(无)
递交数
0
已通过
0
通过率
?
被复制
3
上传者