Course Schedule III

发表于 | 分类于

Course Schedule III

题目描述：

给定一个数组，数组中包含的数据[a, b]; a代表着课程的所需时间，b代表这个课程必须在这个时间前完成。要求找到能完成最多课程的选课方法和数量。

例子：

具体描述见LeetCode630

解题思路：

这题主要用的想法是贪心；首先我们对数据进行排序，排序的规则是课程结束时间。然后我们利用一个multiset来保存当前选择的每个课程的时间长度和consume来记录我们当前使用的时间长度。然后遍历数组，如果加上当前课程不会超过结束时间就将其加入到multiset和consume中，如果已经超过的情况下，我们将保存课程时间的最后一个数据和当前的课程时间比较，如果较大的情况下，说明我们可以放弃上一个选择的课程然后选择当前课程。因为我们总是需要尽可能的在一个时间段内选择更多的花费时间长度小的课程这样我们就能选择更多的课程。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int scheduleCourse(vector<vector<int>>& courses) {
        sort(courses.begin(), courses.end(), [](vector<int> a, vector<int>b){ return a.back() < b.back();});
        multiset<int> cls;
        int consume = 0;
        
        for (int i = 0; i < courses.size(); i++){
            if (consume + courses[i].front() <= courses[i].back()){
                consume += courses[i].front();
                cls.insert(courses[i].front());
            }else if (*cls.rbegin() > courses[i].front()){
                consume += courses[i].front() - *cls.rbegin();
                cls.erase(--cls.end());
                cls.insert(courses[i].front());
            }
        }
        return cls.size();
    }
};