算法笔记之优先队列——课程表 III

优先队列（堆）的经典应用，记录一下。

题目描述

LeetCode.630. 课程表 III

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

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

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

解题思路

此题利用了贪心的思想，考虑两门课的场景，我们要先学哪一门呢？我们需要先学截至日期更近的那门课。

因此，我们可以将所有课程按截止时间排序，然后依次学习。但是，这样并不能保证我们前面遍历到的课程学习了，后面的课程就满足学习条件。

因为题目要求了返回能够学习的最大课程数目，所以，我们应该优先选择学习时长更短的课程。

因此，我们可以使用优先级队列（大根堆）来维护已经选择了的课程，当出现冲突的时候，我们比较堆顶元素与待选择元素的学习时长，选择时长更短的课程进行学习。

Java代码

class Solution {
    public int scheduleCourse(int[][] courses) {
        // 按截至时间排序
        Arrays.sort(courses, (a, b) -> (a[1] - b[1]));
        // 优先队列，大根堆，按时长排序，更长的在顶部
        PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> (b[0] - a[0]));
        int time = 0;
        for(int[] course : courses) {
            if(time + course[0] > course[1]) {
                if(!pq.isEmpty()) {
                    // 取堆顶元素
                    int[] current = pq.peek();
                    // 贪心策略，去掉时长最大的
                    if(current[0] > course[0]) {
                        pq.poll();
                        pq.offer(course);
                        time = time - current[0] + course[0];
                    }
                }
            } else {
                pq.offer(course);
                time += course[0];
            }
        }
        return pq.size();
    }
}