Course Schedule III

题目来源
一道课程选择的问题,给你一堆课程,告诉你每个课程上课所需时间以及停课日期。让你如何选择尽可能多的课。
我没想出来怎么做,看了下讨论区,用的最大堆的方法。先将课程以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();
    }
};
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容