美文网首页
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

    题目来源一道课程选择的问题,给你一堆课程,告诉你每个课程上课所需时间以及停课日期。让你如何选择尽可能多的课。我没想...

  • [刷题防痴呆] 0630 - 课程表 III (Course S

    题目地址 https://leetcode-cn.com/problems/course-schedule-iii...

  • 8.27 - hard - 110

    630. Course Schedule III 现排序,再用heap,很多greedy的问题都可以这样来做。基本...

  • 刷题(15)Topological Sort

    leetcode207.Course Schedule ,210.Course Schedule ii 基本上都是...

  • 算法技巧篇

    此篇记录我刷题中觉得比较奇妙,值得记录的题或者解法。 Course Schedule III一道课程选择的问题,给...

  • Class Schedule Card

    Course schedule, online record every day of the course ev...

  • Course Schedule

    https://leetcode.com/problems/course-schedule/给定一个数字N和一个二...

  • 2019-09-29

    Course Schedule Longest Repeating Character Replacement G...

  • 2019-01-21

    LeetCode 207. Course Schedule Description There are a tot...

  • Privacy Policy

    The "Course Schedule-Daily Record" app respects and prote...

网友评论

      本文标题:Course Schedule III

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