Every day a Leetcode
題目來源：630. 課程表 III
解法1：反悔貪心
經驗告訴我們，在準備期末考試的時候，先考的課程先準備。同理，lastDay 越早的課程，應當越早上完。但是，有的課程 duration 比較長，上完需要花很多時間，可能把這些時間花在其它課程，早就上完好幾門課了。
看上去，找不到一個合適的貪心策略。別放棄！順著這個思路，如果我們可以「反悔」呢？
按照 lastDay 從小到大排序，然后遍歷數組 courses。比如先上完 duration=7 的課和 duration=10 的課，后面遍歷到了 duration=4 的課，但受到 lastDay 的限制，無法上 duration=4 的課。此時，我們可以「撤銷」前面 duration 最長的課，也就是 duration=10 的課，這樣就可以上 duration=4 的課了！雖然能上完的課程數目沒有變化，但是由于我們多出了 10?4=6 天時間，在后續的遍歷中，更有機會上完更多的課程。
在上面的討論中，我們需要維護一個數據結構，來幫助我們快速找到 duration 最長的課程。這可以用優先隊列（大根堆）解決。
代碼：
/** @lc app=leetcode.cn id=630 lang=cpp** [630] 課程表 III*/// @lc code=start
class Solution
{
public:int scheduleCourse(vector<vector<int>> &courses){// 大根堆priority_queue<int> pq;int day = 0; // 已消耗時間sort(courses.begin(), courses.end(), [](const auto &a, const auto &b){return a[1] < b[1]; // 按照 lastDay 從小到大排序});for (vector<int> &course : courses){int duration = course[0], lastDay = course[1];if (day + duration <= lastDay){// 沒有超過 lastDay，直接學習day += duration;pq.push(duration);}// 該課程的時間比之前的最長時間要短else if (!pq.empty() && duration < pq.top()){// 反悔，撤銷之前 duration 最長的課程，改為學習該課程// 節省出來的時間，能在后面上完更多的課程day -= pq.top();pq.pop();day += duration;pq.push(duration);}}return pq.size();}
};
// @lc code=end
結果：
復雜度分析：
時間復雜度：O(nlogn)，其中 n 為數組 courses 的長度。排序需要 O(nlog?n) 的時間；遍歷 courses\textit{courses}courses 時，每次操作堆都需要 O(log?n) 的時間。總的時間復雜度為 O(nlog?n)。
空間復雜度：O(n)，其中 n 為數組 courses 的長度。
