题目描述：

这里有 n 门不同的在线课程，按从 1 到 n 编号。给你一个数组 courses ，其中 courses[i] = [durationi, lastDayi] 表示第 i 门课将会 持续 上 durationi 天课，并且必须在不晚于 lastDayi 的时候完成。

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

返回你最多可以修读的课程数目。

示例 1：

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

示例 2：

输入：courses = [[1,2]]
输出：1

示例 3：

输入：courses = [[3,2],[4,3]]
输出：0

提示:

• 1 <= courses.length <= 10^4
• 1 <= durationi, lastDayi <= 10^4

解法一：优先队列 + 贪心

算法思路：

• 我们首先可以按照课程的结束时间进行升序排序，并依次挑选课程按照顺序进行学习。
• 定义一个 total 来记录已选择的课程总共耗费的时间，使用优先队列记录已选择的课程。
• 如果一门课程的耗时 + total 小于它的结束时间，则入列。
• 当某门课的耗时和 total 之和大于该门课程的结束时间时，这门课不能选择。
• 此时可以用这门课与已选则的耗时最长的课程进行比较，如果此门课程耗时更短，则替换掉这门课。（对于下一门课程来说，这种替换使得 total 总是在减小，是可以接受的。）
• 最后队列中课程的数目就是答案。

优先队列

优先队列（PriorityQueue）是一种特殊的队列数据结构，其中的元素按照优先级进行排序。优先队列中的元素可以是任意类型，但必须是可比较的（实现了Comparable接口或者通过自定义比较器）。

优先队列的特点是，当元素插入到队列中时，会根据元素的优先级自动调整其在队列中的位置。在优先队列中，元素的优先级通常是通过比较器（Comparator）或者元素自身的自然顺序（实现了Comparable接口）来确定的。

代码实现：

class Solution {
    public int scheduleCourse(int[][] courses) {
        // 按照截止时间从小到大排序
        Arrays.sort(courses, (a, b) -> a[1] - b[1]);
        // 降序排列的优先队列
        PriorityQueue<Integer> q = new PriorityQueue<Integer>((a, b) -> b - a);
        // 已选课程的总时间
        int total = 0;
        for(int[] course : courses){
            int ti = course[0], di = course[1];
            // 如果能学，直接学，加入优先队列
            if(total + ti <= di){
                total += ti;
                q.offer(ti);
            } else if(!q.isEmpty() && q.peek() > ti) {
                // 如果不可以学且队列中最长的课更长，替换掉
                total -= q.poll() - ti;
                q.offer(ti);
            }
        }
        // 答案即为队列中的课程数
        return q.size();
    }
}

复杂度分析：

时间复杂度： O(n log n)，排序需要 O(n log n) 的时间，优先队列的单次操作需要 O(log n) 的时间，每个任务会最多被放入和取出优先队列一次，这一部分的时间复杂度为 O(n log n)。因此总时间复杂度也为 O(n log n)。

空间复杂度： O(n)，即为优先队列需要使用的空间。

相关链接

• 630. 课程表 III