题目描述

这里有 $n$ 门不同的在线课程，第 $i$ 门课需要持续上 $duration_i$ 天课，并且必须在不晚于 $lastDay_i$ 的时候完成。

你的学期从第 $1$ 天开始，且不能同时修读两门及两门以上的课程。

给定所有课程的 $duration_i$ 和 $lastDay_i$，求最多可以修读的课程数目。

输入格式

第一行一个整数 $n$，表示课程数量。

接下来 $n$ 行，每行两个整数 $duration_i$ 和 $lastDay_i$，分别表示第 $i$ 门课程的持续时间和最迟完成时间。

输出格式

输出一个整数，表示最多可以修读的课程数目。

样例输入1

4
100 200
200 1300
1000 1250
2000 3200

样例输出1

3

样例输入2

1
1 2

样例输出2

1

样例输入3

2
3 2
4 3

样例输出3

0

数据范围

• $1 \le n \le 10^4$
• $1 \le duration_i, lastDay_i \le 10^4$

说明

本题改编自 LeetCode 630. Course Schedule III（课程表 III），采用标准输入输出，数据为随机生成并经双标程（C++ / Python）交叉校验。

提示

经典「反悔贪心」，时间复杂度 $O(n \log n)$：

1. 将课程按 $lastDay_i$ 升序排序；
2. 依次处理每门课程，先将其加入已选集合（累计耗时增加）；
3. 若累计耗时超过了当前课程的 $lastDay_i$，则反悔：从已选课程中剔除耗时最长的一门（可能刚被剔除的就是刚加入的这一门）；
4. 处理完所有课程后，已选集合的大小即为答案。

正确性关键：按截止时间升序处理后，当前已选集合始终是"前 $i$ 门课中，门数最多且总耗时最小的可行方案"，因此剔除最长耗时的课程总是安全的。