力扣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();}};