美文网首页
Course Schedule III

Course Schedule III

作者: 我叫胆小我喜欢小心 | 来源:发表于2017-08-01 19:25 被阅读28次

    题目来源
    一道课程选择的问题,给你一堆课程,告诉你每个课程上课所需时间以及停课日期。让你如何选择尽可能多的课。
    我没想出来怎么做,看了下讨论区,用的最大堆的方法。先将课程以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();
        }
    };
    

    相关文章

      网友评论

          本文标题:Course Schedule III

          本文链接:https://www.haomeiwen.com/subject/bntdlxtx.html