本文最后更新于 391 天前,其中的信息可能已经有所发展或是发生改变。
题目描述:
这里有 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),即为优先队列需要使用的空间。