ᕕ( ᐛ )ᕗ Jimyag's Blog

LeetCode-630-课程表 3

题目

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

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

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

示例

1
2
3
4
5
6
7
8

输入：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 天完成它，这已经超出了关闭日期。

1
2

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

1
2

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

解答

要尽可能多的课程被选择，我们优先选择结束时间最早的课程，这样才能保证前面的课程是能被选择的，光靠这个进行选择是不行的。例如：[1,2] 、[3, 4]、[2, 5]这三门课的时候，如果按照上述方法进行选择，那么结果是：选择第一个课程，在选择第二个课程时候截止时间到了，不行，只能选择第三号课程。我们观察可以发现，其实可以先选三号课程，在选择 2 号课程。也就是在上述条件的基础上，优先选择**学习时长更短 (duration)**的课程。使用大根堆可以满足我们的要求，我们在选择课程的时候做一判断：

  1. 如果总学习时间 + 当前课程的学习时间<该课程的结束时间，那么这个课可以选择；
  2. 如果不满足条件 1，但是满足，在已经选择的课程中，最长的课程时间>当前的课程持续时间，那么就选择当前的课程，并把之前选择的最长的课程取消选择。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

// 贪心，按照结束时间的进行升序排列
sort(courses.begin(), courses.end(), [](const auto &c0, const auto &c1) {
    return c0[1] < c1[1];
});
// 最长的持续时间在前面
priority_queue<int> maxHeap;
// 优先队列中所有课程的总时间
int hadLearnedTime = 0;

for (const auto &course: courses) {
    int currentCourseDuration = course[0], currentCourseLastDay = course[1];
    //如果总时长不会超过截止时间，那么，当前这门课程可以选择，直接入堆
    if (hadLearnedTime + currentCourseDuration <= currentCourseLastDay) {
        hadLearnedTime += currentCourseDuration;
        maxHeap.push(currentCourseDuration);
    } else if (!maxHeap.empty() && maxHeap.top() > currentCourseDuration) {
        // 出现冲突，优先选择学习时长更短的课程
        hadLearnedTime = hadLearnedTime - maxHeap.top() + currentCourseDuration;
        maxHeap.pop();
        maxHeap.push(currentCourseDuration);
    }
}
return maxHeap.size();

#困难 #贪心

目录