脚本宝典收集整理的这篇文章主要介绍了leetcode-630. 课程表 III,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
示例: 输入: [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]] 输出: 3 解释: 这里一共有 4 门课程, 但是你最多可以修 3 门: 首先, 修第一门课时, 它要耗费 100 天,你会在第 100 天完成, 在第 101 天准备下门课。 第二, 修第三门课时, 它会耗费 1000 天,所以你将在第 1100 天的时候完成它, 以及在第 1101 天开始准备下门课程。 第三, 修第二门课时, 它会耗时 200 天,所以你将会在第 1300 天时完成它。 第四门课现在不能修,因为你将会在第 3300 天完成它,这已经超出了关闭日期。
/* (1) 按照deadline从小到大排序, 先学习deadline靠前的不吃亏,理想情况下:所有前一门课的deadline和下一门课必须开始的的时间不相交,那么可以修所有的课,比如下面3门课: [100, 200], [200, 400], [150, 500] (2) 当要学习下一门课时,发现当前学习的天数(第几天) 加上 准备学习的这门课的持续时间,会超过准备学习这门课的deadline, 怎么办? 肯定是把修过的课里面的持续时间最长的课程给去掉,对于本次来说加一个,去一个,是没有多修课程的;但是有可能多后续的就有收益,因为你去掉了最长的课程, 这样就腾出了最多的空间。 */ class Solution { public: static bool cmp(vector<int> &a, vector<int> &b){ if(a[1]!=b[1]) return a[1]<b[1]; else return a[0]<b[0]; } int scheduleCourse(vector<vector<int>>& courses) { if(courses.size()==0) return 0; sort(courses.begin(), courses.end(), cmp); // 结束时间从小到大排序 PRiorITy_queue<int ,vector<int>, less<int>> maxheap; // 持续时间大根堆 int cot = 0; int j = 0; int curtime = 0; for(int i = 0; i < courses.size(); i++){ // 如果当前时间加上学习持续的时间小于结束时间,说明可以学习 if(curtime+courses[i][0]<=courses[i][1]){ maxheap.push(courses[i][0]); curtime = curtime + courses[i][0]; }else{ // 说明不可以学习,那我先学习这门课程,再将堆里面持续时间最长的去掉 maxheap.push(courses[i][0]); curtime = curtime + courses[i][0]; int dur = maxheap.top(); curtime = curtime - dur; maxheap.pop(); } } return maxheap.size(); } };
以上是脚本宝典为你收集整理的leetcode-630. 课程表 III全部内容,希望文章能够帮你解决leetcode-630. 课程表 III所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。