链接:

630. 课程表 III

题意

一个课程花费ai天,需要在bi天之前修好才算成功,求最多能修几个课

ddl越靠后的应该越晚做,所以先按照b排序(这还用问为什么吗?

然后通过维护一个优先队列存储目前已经修的课程,按照a排序,花费时间越多的越不划算

这是我们可以发现,越后面进来的课,ddl越晚,那么当这个后面来的课a大于队列内的数字时,不能修

当这个后面来的课a小于队列内的数字时,是更优解,替换队列内的最大数(由于用时短,ddl晚,则一定合法

实际代码:

#includeusing namespace std;static bool cmp(vector& lhs,vector& rhs){if(lhs[1]==rhs[1]) return lhs[0]<rhs[0];else return lhs[1]<rhs[1];}int scheduleCourse(vector<vector>& courses){sort(courses.begin(),courses.end(),cmp);priority_queuep_q;int sum=0;for(auto& course:courses){int need=course[0],ddl=course[1];if(sum+needneed){sum-=p_q.top()-need;p_q.pop();p_q.push(need);}}return p_q.size();}

限制:

  • 1 <= courses.length <= 104
  • 1 <= durationi, lastDayi <= 104