LeetCode 630. 课程表 III - 优先队列&贪心

题目描述

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

你的学期从第 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

解题思路

一开始排个序，无脑想用DP，但是仔细一想如果后续存在（大量）duration小、lastDay大的高“性价比”课程，那就要反复考虑，复杂度和我尝试模拟一下的脑袋估计都会炸掉。后来看到别人提到贪心，茅塞顿开，只能说还是钻牛角尖了。

还是按照最开始的思路先排序，不过只需要根据lastDay从小到大排，因为涉及到贪心我们只需要关注lastDay这个限制条件，这个按下不表，后面就清楚了。

贪心和背包DP相似的地方就是做选择，要或是不要。遍历时我们要默认一个条件，就是上面排序时提到的，当前的lastDay一定是大于等于前面已经遍历过了的。

那么什么情况下我们选择要呢？首先，当前课程加入课表，也就是我们的优先队列q，我们当前的总duration不会超过该课程的lastDay，那么我们就可以直接要这门课。这很好理解，我们的课表q最基本的就是需要一直维持里面的课是符合要求的，那么当一个直接符合能在lastDay前结课的课程出现，不要白不要。

但是当直接加入课表会造成逾期，我们就要开始取舍了。这里我们简化一下概念会比较好理解。同样的duration，肯定是lastDay越大我们越想要；同样的lastDay，肯定是duration越小我们越想要。那么，在遍历的过程中，由于提前通过排序使得当前的lastDay一定大于等于之前的，我们就只需要关注当前课程与课表中duration最大的课程之间的取舍了。

这里就是为什么选用优先队列的原因了，因为优先队列的队首默认是最大的元素，我们只需要拿当前课程的duration与队首（前提是队列不为空），也就是我们课表中当前duration最大的课程对比一下，然后选取duration较小的、舍弃较大的就行了。

class Solution {
public:
    int scheduleCourse(vector<vector<int>>& courses) {
        sort(courses.begin(), courses.end(), [](const auto &course1, const auto& course2) {
            return course1[1] < course2[1];
        });  // 保证后续遍历时，当前deadline一定大于等于已经遍历过的

        priority_queue<int> q;
        int total_time = 0;
        for (auto &course : courses) {  // 贪心
            if (total_time + course[0] <= course[1]) {  // 能够满足当前deadline，无脑入队
                total_time += course[0];
                q.push(course[0]);
            }
            else if (!q.empty() && q.top() > course[0]) {  // 和课表中最不具“性价比”的课程作取舍
                total_time -= q.top() - course[0];
                q.pop();
                q.push(course[0]);
            }
        }

        return q.size();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24