湖南郴州新网,百度seo网站优化服务,石家庄哪有个人建站的,项目推广app链接#xff1a;
630. 课程表 III
题意
一个课程花费ai天#xff0c;需要在bi天之前修好才算成功#xff0c;求最多能修几个课
解#xff1a;
ddl越靠后的应该越晚做#xff0c;所以先按照b排序#xff08;这还用问为什么吗#xff1f;
然后通过维护一个优先队列存…链接
630. 课程表 III
题意
一个课程花费ai天需要在bi天之前修好才算成功求最多能修几个课
解
ddl越靠后的应该越晚做所以先按照b排序这还用问为什么吗
然后通过维护一个优先队列存储目前已经修的课程按照a排序花费时间越多的越不划算
这是我们可以发现越后面进来的课ddl越晚那么当这个后面来的课a大于队列内的数字时不能修
当这个后面来的课a小于队列内的数字时是更优解替换队列内的最大数由于用时短ddl晚则一定合法
实际代码
#includebits/stdc.h
using namespace std;
static bool cmp(vectorint lhs,vectorint rhs)
{if(lhs[1]rhs[1]) return lhs[0]rhs[0];else return lhs[1]rhs[1];
}
int scheduleCourse(vectorvectorint courses)
{sort(courses.begin(),courses.end(),cmp);priority_queueintp_q;int sum0;for(auto course:courses){int needcourse[0],ddlcourse[1];if(sumneedddl){sumneed;p_q.push(need);}else if(!p_q.empty() p_q.top()need){sum-p_q.top()-need;p_q.pop();p_q.push(need);}}return p_q.size();
}
限制
1 courses.length 1041 durationi, lastDayi 104