#O1092. 任务调度

任务调度

题目描述

单机上有 nn 个任务,第 ii 个任务需要 tit_i 单位时间,必须在 did_i 时刻之前完成(可以在 did_i 时刻恰好完成)。机器同一时刻只能执行一个任务,任务之间不中断。求最多能按时完成多少个任务。

输入格式

第一行一个整数 nn。

接下来 nn 行,每行两个整数 ti,dit_i,d_i。

输出格式

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

样例 #1

样例输入 #1

5
2 5
1 3
4 9
3 7
6 8

样例输出 #1

4

数据规模与约定

数据范围 说明
1≤n≤1051 \le n \le 10^5 任务数
1≤ti≤10001 \le t_i \le 1000 耗时
ti≤di≤109t_i \le d_i \le 10^9 截止时间
  • 按截止时间从早到晚排序,能塞就塞。