題目網址：https://leetcode.cn/problems/course-schedule-iii/

題意：有 n 個不同的課程, 編號從 1 到 n。給一整數 array course, 其中 courses[i] = [duration_i, lastDay_i] 代表第 i 門課程會持續 duration_i 天, 且須在 lastDay_i 之前完成。

學期從第 1 天開始, 且不得同時修習兩門(含)以上的課程。

返回最多可修習的課程數目。

Solution：

想法：利用 Greedy + Heap, 由於我們希望能修習的課越多越好, 因此我們要先將課程根據 deadline 由小到大排序, 因為 deadline 越是緊急的課越應該優先完成, 完成後才接著去安排 deadline 相對寬鬆的課

  • 將所有課程根據 deadline 由小到大排序
  • 用 max heap q 維護目前取的課程中 duration 最長的課
  • 按照 deadline 的順序, 一一嘗試加入課程。一旦有課程無法在 deadline 前完成, 則取消掉目前取的課程中 duration 最長的課

e.g. courses = [[3, 5], [4, 7], [2, 8]]

  • 第一天取 [3, 5] 在第三天時修完第一門, 然後取 [4, 7] 於第 7 天完成第二門, 接著取 [2, 8], 但是第三門無法在 deadline 前完成, 因為 7 + 2 = 9 > 8
  • 我們會希望在修習相同課程數的條件下, days 能越小越好, 因為這樣後面課程才越有機會在 deadline 前完成
  • 所以我們取消掉 [4, 7], 因為它的 duration 最長。此時我們取了 [3, 5] 和 [2, 8] 這兩門課只花了 5 天, 而非 [3, 5] 和 [4, 7] 這樣需花 7 天。
class Solution {
public:
    int scheduleCourse(vector<vector<int>>& courses) {
        const auto cmp = [](const vector<int>& c1, const vector<int>& c2){
            return c1[1] < c2[1];
        };

        sort(courses.begin(), courses.end(), cmp);

        int days = 0; // 從第一天就開始修課
        priority_queue<int> q; // max heap, 維護目前取的課程中 duration 最長的課

        for (const auto& course : courses) {
            int duration = course[0], lastDay = course[1];

            // 先嘗試取當前課程
            q.emplace(duration);
            days += duration;

            // 若超出 deadline, 則取消 q 中 duration 最長的課程
            if (days > lastDay) {
                days -= q.top();
                q.pop();
            }
        }

        return q.size(); // 代表最後取了幾門課
    }
};
  • time：$O(n \cdot log(n))$ ➔ 每次 heap 取出元素後, 需花 $O(log(n))$ 調整 heap, 總共取 n 次
  • space：$O(n)$ ➔ q 中元素不超過 n 個