鏈接：

630. 課程表 III

題意

一個(gè)課程花費(fèi)ai天，需要在bi天之前修好才算成功，求最多能修幾個(gè)課

解：

ddl越靠后的應(yīng)該越晚做，所以先按照b排序（這還用問(wèn)為什么嗎？

然后通過(guò)維護(hù)一個(gè)優(yōu)先隊(duì)列存儲(chǔ)目前已經(jīng)修的課程，按照a排序，花費(fèi)時(shí)間越多的越不劃算

這是我們可以發(fā)現(xiàn)，越后面進(jìn)來(lái)的課，ddl越晚，那么當(dāng)這個(gè)后面來(lái)的課a大于隊(duì)列內(nèi)的數(shù)字時(shí)，不能修

當(dāng)這個(gè)后面來(lái)的課a小于隊(duì)列內(nèi)的數(shù)字時(shí)，是更優(yōu)解，替換隊(duì)列內(nèi)的最大數(shù)（由于用時(shí)短，ddl晚，則一定合法

實(shí)際代碼：

#include<bits/stdc++.h>
using namespace std;
static bool cmp(vector<int>& lhs,vector<int>& rhs)
{if(lhs[1]==rhs[1]) return lhs[0]<rhs[0];else return lhs[1]<rhs[1];
}
int scheduleCourse(vector<vector<int>>& courses)
{sort(courses.begin(),courses.end(),cmp);priority_queue<int>p_q;int sum=0;for(auto& course:courses){int need=course[0],ddl=course[1];if(sum+need<=ddl){sum+=need;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 <= 104
• 1 <= durationi, lastDayi <= 104