題目來(lái)源
一道課程選擇的問(wèn)題倍宾，給你一堆課程赁严，告訴你每個(gè)課程上課所需時(shí)間以及停課日期。讓你如何選擇盡可能多的課牡整。
我沒(méi)想出來(lái)怎么做藐吮，看了下討論區(qū)，用的最大堆的方法逃贝。先將課程以end time排個(gè)序谣辞，然后用貪心的方法，每次選取一門課沐扳，先入堆泥从，然后判斷是否可行，假如不可行沪摄，那么就把已選的耗時(shí)最長(zhǎng)的去掉躯嫉，然后繼續(xù)選，題目簡(jiǎn)單但是還挺精妙的杨拐。
代碼如下：
class Solution {
public:
int scheduleCourse(vector<vector<int>>& courses) {
sort(courses.begin(), courses.end(), [](vector<int> a, vector<int> b) {return a[1] < b[1];});
int now = 0, n = courses.size();
priority_queue<int> heap;
for (int i=0; i<n; i++) {
heap.push(courses[i][0]);
now += courses[i][0];
if (now > courses[i][1]) {
now -= heap.top();
heap.pop();
}
}
return heap.size();
}
};
