本文涉及知識點

貪心 反悔堆 優先隊列 臨項交換

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 <= 10⁴
1 <= durationi, lastDayi <= 10⁴

臨項交換+反證法+決策包容性

證明過程比較復雜，結論如下：
性質一：只需要按結束時間升序枚舉。
性質二：按性質一排序后，前i門課的最佳解：a，學的課程多更優。 b，相同課程結束時間早的更優。

利用臨項交換證明性質一

令最優解，按順序為：{{t1,d1},{t2,d2}$?$ {tk,dk}}
$?$i ，如果di < d{i+1} ，則調整兩者的順序。不失一般性，假定i為1。
令調整前: 第x天開始執行{t1,d1}，則說明：
x + t1 -1 <= d1 式子一
x + t1 + t2 -1 <= d2 式子二
式子二，結合t1 >=1 $\to$ x + t2 -1 <= d2
式子二結合假定d2 < d1 $\to$ 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門，則最優解一定優于某方案。
余下情況，最優解的后續狀態有如下兩種可能：
$$\{\begin{array}{llc}一，最優解的k門。& & k門的用時都小于等于第i+1門。\\ 二最優解的(k?1)門+第(i+1)門。& & other\end{array}$$
某方案只有情況二，即：最優解方案包容某方案。

代碼

思路

小根堆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++**實現。