本文涉及知识点
贪心 反悔堆 优先队列 临项交换
Leetcode630. 课程表 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
临项交换+反证法+决策包容性
证明过程比较复杂，结论如下：
性质一：只需要按结束时间升序枚举。
性质二：按性质一排序后，前i门课的最佳解：a，学的课程多更优。 b，相同课程结束时间早的更优。
利用临项交换证明性质一
令最优解，按顺序为：{{t1,d1},{t2,d2}
⋯
\cdots
⋯ {tk,dk}}
∀
\forall
∀i ，如果di < d{i+1} ，则调整两者的顺序。不失一般性，假定i为1。
令调整前: 第x天开始执行{t1,d1}，则说明：
x + t1 -1 <= d1 式子一
x + t1 + t2 -1 <= d2 式子二
式子二，结合t1 >=1
→
\rightarrow
→ x + t2 -1 <= d2
式子二结合假定d2 < d1
→
\rightarrow
→ x +t1 + t2 -1 <= d1
即调整后也合法。
所有相邻的两项调整后，di升序。故：我们枚举的时候只需要考虑di升序。
反证法和决策包容性证明性质二
最佳结果：
学的课程多优于学的课程少。
学的课程相等，所用时间短的更优，早结束。
那么推导第i+1门课程的过程如下：
如果学完前i门后，能学第i+1门课程，则将第i+1门课加到最佳课程中。
否则，最佳课程中有课程的用时多于第i+1门课且用时最多的课，替换成第i+1门课。
反证法
假定前i门课的最优解是k门课，某个方案只有k-1门课。有如下推论：
一，某方案一定不劣与最优解的k-1门最短的课，否则用最优解的最短k-1门替换某方案。
二，某方案一定不优与最优解的k-1门最短的课，优于最短的k-1门，则优于任意k-1门。我们将最优解的前k-1替换成某方案会更优，与最优解矛盾。如果有重复课程都删除，则删除后，分别有k1和k1-1门课，仍然符合结论。
故：某方案就是最优解最短的k-1门课。
决策包容性
某方案如果不选择第i+1门课，则一定劣与最优解。
如果最优接的后续状态，能够选择k+1门，则最优解一定优于某方案。
余下情况，最优解的后续状态有如下两种可能：
{
一，最优解的
k
门。
k
门的用时都小于等于第
i
+
1
门。
二最优解的
(
k
−
1
)
门
+
第
(
i
+
1
)
门。
o
t
h
e
r
\begin{cases} 一，最优解的k门。&& k门的用时都小于等于第i+1门。 \\ 二 最优解的(k-1)门+ 第(i+1)门。 && other \\ \end{cases}
{一，最优解的k门。二最优解的(k−1)门+第(i+1)门。k门的用时都小于等于第i+1门。other
某方案只有情况二，即：最优解方案包容某方案。
代码
思路
小根堆headEndNeed记录 {ti,d1}
我们处理完前i项课程的最终结果放到：headRes中。use记录最佳结果的总用时。
学习完k+1门课，用是use + need，则学完最后一天的时间为use+need，从1开始。
时间复杂度： O(nlogn) 每门课的操作时间是log(n)。
核心代码
class Solution {
public:
int scheduleCourse(vector<vector<int>>& courses) {
priority_queue<std::pair<int, int>, vector< std::pair<int, int>>, greater<>> headEndNeed;
for (const auto& v : courses) {
headEndNeed.emplace(make_pair(v[1], v[0]));
}
priority_queue<int> headRes;
int use = 0;
while (headEndNeed.size()) {
auto [end, need] = headEndNeed.top();
headEndNeed.pop();
if (use + need <= end) {
headRes.emplace(need);
use += need;
}
else {
if (headRes.size() && (headRes.top() > need)) {
use += (need - headRes.top());
headRes.pop();
headRes.emplace(need);
}
}
}
return headRes.size();
}
};
单元测试
template<class T1, class T2>
void AssertEx(const T1& t1, const T2& t2)
{
Assert::AreEqual(t1, t2);
}
template<class T>
void AssertEx(const vector<T>& v1, const vector<T>& v2)
{
Assert::AreEqual(v1.size(), v2.size());
for (int i = 0; i < v1.size(); i++)
{
Assert::AreEqual(v1[i], v2[i]);
}
}
template<class T>
void AssertV2(vector<vector<T>> vv1, vector<vector<T>> vv2)
{
sort(vv1.begin(), vv1.end());
sort(vv2.begin(), vv2.end());
Assert::AreEqual(vv1.size(), vv2.size());
for (int i = 0; i < vv1.size(); i++)
{
AssertEx(vv1[i], vv2[i]);
}
}
namespace UnitTest
{
vector<vector<int>> courses;
TEST_CLASS(UnitTest)
{
public:
TEST_METHOD(TestMethod00)
{
courses = { {100, 200}, {200, 1300}, {1000, 1250}, {2000, 3200} };
auto res = Solution().scheduleCourse(courses);
AssertEx(3, res);
}
TEST_METHOD(TestMethod01)
{
courses = { {1,2} };
auto res = Solution().scheduleCourse(courses);
AssertEx(1, res);
}
TEST_METHOD(TestMethod02)
{
courses = { {3,2},{4,3} };
auto res = Solution().scheduleCourse(courses);
AssertEx(0, res);
}
};
}
扩展阅读
视频课程
先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关推荐
| 我想对大家说的话 |
|---|
| 《喜缺全书算法册》以原理、正确性证明、总结为主。 |
| 按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。 |
| 有效学习：明确的目标 及时的反馈 拉伸区（难度合适） 专注 |
| 闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
