来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/course-schedule-iii
题目描述
这里有 n 门不同的在线课程，按从 1 到 n 编号。给你一个数组 courses ，其中 courses[i] = [durationi, lastDayi] 表示第 i 门课将会 持续 上 durationi 天课，并且必须在不晚于 lastDayi 的时候完成。
你的学期从第 1 天开始。且不能同时修读两门及两门以上的课程。
返回你最多可以修读的课程数目。
示例 1： 输入：courses = [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]] 输出：3 解释： 这里一共有 4 门课程，但是你最多可以修 3 门： 首先，修第 1 门课，耗费 100 天，在第 100 天完成，在第 101 天开始下门课。 第二，修第 3 门课，耗费 1000 天，在第 1100 天完成，在第 1101 天开始下门课程。 第三，修第 2 门课，耗时 200 天，在第 1300 天完成。 第 4 门课现在不能修，因为将会在第 3300 天完成它，这已经超出了关闭日期。 示例 2： 输入：courses = [[1,2]] 输出：1 示例 3： 输入：courses = [[3,2],[4,3]] 输出：0 提示: 1 <= courses.length <= 104 1 <= durationi, lastDayi <= 104
解题思路
使用贪心的思路，尽早学习结束时间较早的科目。首先根据截止时间来将课程排序。
然后依次尝试学习课程，判断总时间是否满足截止日期，如果满足截止日期，那么学习这门课，如果不满足，就是查找之前的课程中是否有比这节课时间长的课程，替换时间最长的课程，替换后的课程数目不变，但是课程持续时间会变短，更有利于之后课程的学习。
源码展示
class Solution { public: int scheduleCourse(vector<vector<int>>& courses) { sort(courses.begin(), courses.end(), [](const auto& c0, const auto& c1) { return c0[1] < c1[1]; }); priority_queue<int> qiCounses; int iSumT = 0; for(auto c: courses) { if(iSumT + c[0] <= c[1]) { qiCounses.push(c[0]); iSumT += c[0]; } else { if(!qiCounses.empty() && c[0] < qiCounses.top()) { iSumT = iSumT + c[0] - qiCounses.top(); qiCounses.pop(); qiCounses.push(c[0]); } } } return qiCounses.size(); } };
运行结果
