题目来源
一道课程选择的问题,给你一堆课程,告诉你每个课程上课所需时间以及停课日期。让你如何选择尽可能多的课。
我没想出来怎么做,看了下讨论区,用的最大堆的方法。先将课程以end time排个序,然后用贪心的方法,每次选取一门课,先入堆,然后判断是否可行,假如不可行,那么就把已选的耗时最长的去掉,然后继续选,题目简单但是还挺精妙的。
代码如下:
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();
}
};
网友评论