力扣630.课程表 II
力扣630.课程表 II
-
反悔堆
- 将课程按照结束时间从大到小排序
- 每次取一个判断当前是否能学完该课程
- 如果能学完就将持续时间加入堆 更新答案
- 如果学不完就判断该课程持续时间是否比之前学过的最大的还大
- 用时更短的话就将旧的弹出
-
class Solution {public:int scheduleCourse(vector<vector<int>>& courses) {sort(courses.begin(),courses.end(),[](const auto &a,const auto &b){return a[1]<b[1];});priority_queue<int> pq;int day=0;for(auto &c:courses){int dur = c[0],las = c[1];if(day + dur <= las){day += dur;pq.push(dur);}//学不完 判断是否更优else if(!pq.empty() && dur < pq.top()){//等价于day - pq.top() + durday -= pq.top() - dur;pq.pop();pq.push(dur);}}return pq.size();}};