题目描述

这里有 n 门不同的在线课程，他们按从 1 到 n 编号。每一门课程有一定的持续上课时间（课程时间）t 以及关闭时间第 d 天。一门课要持续学习 t 天直到第 d 天时要完成，你将会从第 1 天开始。

给出 n 个在线课程用 (t, d) 对表示。你的任务是找出最多可以修几门课。

样例

输入: [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]]
输出: 3
解释: 
这里一共有 4 门课程, 但是你最多可以修 3 门:
首先, 修第一门课时, 它要耗费 100 天，你会在第 100 天完成, 在第 101 天准备下门课。
第二, 修第三门课时, 它会耗费 1000 天，所以你将在第 1100 天的时候完成它, 以及在第 1101 天开始准备下门课程。
第三, 修第二门课时, 它会耗时 200 天，所以你将会在第 1300 天时完成它。
第四门课现在不能修，因为你将会在第 3300 天完成它，这已经超出了关闭日期。

注意

• 整数 1 <= d, t, n <= 10000。
• 你不能同时修两门课程。

算法

(贪心，堆) $O(n \log n)$

1. 首先考虑两门课的(t1, d1) 和 (t2, d2) 的情况，不妨假设 d1 < d2，并且 t1 < d1 && t2 < d2。
2. 如果 t1 + t2 <= d1，则两门课随意安排都可以上。
3. 如果 t1 + t2 > d1 && t1 + t2 <= d_2，则上完第一门课后再上第二门课。
4. 如果 t1 + t2 > d2，则两门课只能上一门，这里当然会选择上时间短的那一门。
5. 故可以根据结束时间 d 排序，维护大根堆记录下选过的每个课的时间；
6. 从头开始遍历课程，维护总的上课时间 tot。
7. 若 tot 加上当前课的时间小于等于当前课 i 的结束时间，则直接将课加入到选课列表中，并记录在大根堆里。
8. 若 tot 加上当前课的时间大于当前课 i 的结束时间，则考虑大根堆中耗时最长的课 top，如果 top 的耗时比当前课程 i 要长，则替换为当前课程 i；否则不替换。

时间复杂度

• 排序时间复杂度为 $O(n \log n)$，枚举课程需要 $O(n)$，每次访问单调队列需要 $O(\log n)$，故总时间复杂度为 $O(n \log n)$。

C++ 代码

class Solution {
public:
    static bool cmp(vector<int> &x, vector<int> &y) {
        return x[1] < y[1];
    }
    int scheduleCourse(vector<vector<int>>& courses) {
        int n = courses.size();
        sort(courses.begin(), courses.end(), cmp);
        priority_queue<int> heap;
        int tot = 0;
        for (int i = 0; i < n; i++) {
            if (tot + courses[i][0] <= courses[i][1]) {
                heap.push(courses[i][0]);
                tot += courses[i][0];
            }
            else if (!heap.empty()) {
                if (heap.top() > courses[i][0]) {
                    tot = tot - heap.top() + courses[i][0];
                    heap.pop();
                    heap.push(courses[i][0]);
                }
            }
        }
        return heap.size();
    }
};