题目描述
输入:二维数组,每行为课程持续上课时间t以及关闭时间d
输出:可以修的最大课程数
样例
见原题
算法1
(贪心) $O(nlogn)$
状态表示:
贪心题,首先从直觉开始考虑,完成课程时倾向于先完成关闭时间更早也就是deadline更早的课程。
因此首先将课程任务按关闭时间从小到大进行排序。
$f(i)$:考虑按关闭时间排序后前i个课程的所有合法方案数量
属性:数量
状态计算:
排完序之后,再根据题目要求,我们需要选择可以修最大课程数的方案,因此需要满足:1、选的个数最多。但这样还不够,考虑到贪心转移的性质,我们必须在每一步都选择局部最优的子方案,否则即使在当前状态下为数量最优,在转移到下一状态后就可能错失最优解,因此在满足1的基础上,还需要满足:2、总用时最小(每种用时个数相同)。这样才能既保证选择课程数量最多又不会导致在转移的过程中用时过大错过最优解,选择局部最优的方案集合。之所以要令每种用时个数相同,是为了节省记录状态的数量。
接下来进行具体转移的计算。
当可以插入新课程$i$时,$$f(i)=f(i-1)+1$$ 此时满足:
1、选的个数最多,因为可以选的时候总是选择他加进去最好;
2、总用时最小(每种用时个数相同),因为第i个课程的用时是固定的,因此无法改变,
只能改变前$i-1$个课程时间的总和。又由于我们前面假设时取得是满足总用时最小的方案集合,$f(i-1)$的总用时也是最小的,因此$f(i)$也满足总用时最小。
当不可以插入新课程$i$(插进来会导致总时长超过课程关闭时间)时,$$f(i)=f(i-1)$$ 满足:1、选的个数最多。因为此时大不了就不学$i$,学的课程数量与之前保持一致。
对于2、总用时最小(每种用时个数相同),我们可以先假设把第$i$个课程加进来,加进来之后再去掉所有加进来的课程中持续上课时间$t$最大的那个课程(这个课程有可能是第$i$个课程,也有可能是前面的$i-1$个课程之一)来满足在不改变课程数量的同时,总用时最小。因为我们的$f(i-1)$方案集合是满足总时长要求的,因此在加进来第$i$个课程后再去掉持续时长最大的一个课程,只会使得$f(i)$的总时长小于等于$f(i-1)$(在去掉第$i$个课程或与其时长相等的课程时相等)(当存在多个最大持续时长时,去掉任意一个也并不会影响我们的最优解数量)
C++ 代码
class Solution {
public:
int scheduleCourse(vector<vector<int>>& courses) {
//使用lambda函数进行sort
sort(courses.begin(),courses.end(),[](vector<int> &c1,vector<int> &c2){
return c1[1]<c2[1];
});
//大顶堆,小顶堆为priority_queue<int,vector<int>,greater<int>> heap;
priority_queue<int> heap;
//总时长
int t=0;
for(auto &c:courses){
//根据前面分析 无论怎样先假设把我们的i课程插入
t+=c[0];
heap.push(c[0]);
if(t>c[1])//总时长超过课程关闭时间
{
t-=heap.top();
heap.pop();
}
}
return heap.size();
}
};