题目

类型：贪心

解题思路

对于两门课，如果后者的关闭时间较晚，那么先学习前者，再学习后者，总是最优的。
假设duration数组是这样的 大学物理 [2, 4] 高等数学 [5, 7] 线性代数 [3, 3]
那么，按照策略，我们会先尝试修读线性代数。 然后尝试修读大学物理，这个时候我们发现竟然修了线性代数之后就修不了大学物理了；只能放弃；转而修高等数学发现也没有足够的时间了。
那合理的做法是什么呢？ 就是我们这个时候需要放弃线性代数，因为线性代数和大学物理的权重是没有区别的，既然两者只能修一门，我们应该让当前累计花费的时间更少。
大学物理虽然ddl比线性代数更晚，但它修读的时间也更短，如果已经要放弃一门课了，我们会放弃修读时间更长的。
所以整体思路就是： 优先修读dll近的，放弃的时候则放弃修读时间长的，给之后的课程留更多的时间。
可以用优先队列模拟这个过程；堆顶放修读时间最长的课程；按照ddl升序排列依次修读。
如果可以修读，更新总修读时间。
如果不可修读，看花费最长时间的课程是哪门，我们把它替换掉即可。

代码

class Solution {
    public int scheduleCourse(int[][] courses) {
        // 以结束时间排序
        Arrays.sort(courses, (c1, c2) -> c1[1] - c2[1]);
        // 储存已选择的课程，按照持续时间排序
        PriorityQueue<int[]> heap = new PriorityQueue<>((c1, c2) -> c2[0] - c1[0]);
        int day = 0;
        for (int[] c : courses) {
            if (day + c[0] <= c[1]) {
                // 如果当前课程时间不冲突，将该课程加入队列
                // 这里的不冲突可以理解为，0~day+c[0]这段区间，我们还可以再插入当前一节课
                day += c[0];
                heap.offer(c);
            } else if (!heap.isEmpty() && heap.peek()[0] > c[0]) {
                // 课程时间冲突，且有选过其他课，这时我们找到最长时间的课程，用当前的短课替换了，余出了更多的空区间
                // 所以这里我们余出的时间其实就是两者的持续时间之差，课程变短了，day会前移，这样我们相当于变相给后面的课程增加了选择的区间
                day -= heap.poll()[0] - c[0];
                heap.offer(c);
            }
        }
        return heap.size();
    }
}