一、學習目標

• 了解什麼是「局部最優導向全局最優」的貪心思想，以及何時可用、何時不可用。
• 學會兩個最常見的貪心套路：區間排程（按結束時間排序）、短工優先以最小化完成時間總和。
• 掌握排序 + 一次遍歷與前綴/維持變數的寫法。
• 能以「交換論證（exchange argument）」直觀說明演算法正確性。

二、觀念說明

貪心是什麼？

在每一步做看起來最佳的選擇（局部最優），期望整體（全局）也最佳。
舉例：選電影場次時，先挑最早結束的，可留更多時間給後續場次。

何時可用？

問題同時具備：

• Optimal substructure：整體最優包含子問題的最優。
• Greedy-choice property：存在一種「當下最佳」的選擇，做了它不會錯過最優解。

常見模式：

• 區間排程：依結束時間升序 → 能選最多場次。
• 最小化完成時間總和：依處理時間（duration）升序（SPT 規則）。
• 能不能到終點／在哪一格加油：維持可達/油量累積的單變數檢查。

交換論證

若最優解不是按照我們的貪心選擇，我們能把其中的某一個元素與我們的選擇「交換」，
並不會讓解變差，一步步交換即可把任意最優解變成貪心解，故貪心解也是最優。

實作要點

八成以上的貪心題都長這樣：

• 排序（通常依結束時間 / 處理時間 / 權重）
• 一次遍歷做決策
• 維持少量狀態（上一個結束時間、目前可達最遠位置、油量差等）

三、CSES實戰演練

題目1 : Movie Festival

原題:
https://cses.fi/problemset/task/1629

題意：給定 n 個電影場次（開始、結束時間），選出最多不重疊場次。

解題思路（貪心）:
依結束時間升序排序；從頭掃描，若當前片的開始時間≥前一部已選片的結束時間，就選它。
直覺：越早結束留給未來的空間越多。

# include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<pair<int,int>> a(n);
    for(auto &p:a){
        cin>>p.first>>p.second;
    }

    //用結束時間排列
    sort(a.begin(), a.end(), [](auto &x, auto &y){
        if (x.second != y.second) return x.second < y.second;
        return x.first < y.first;
    });

    int cnt = 0, last_end = INT_MIN;
    for (auto &p : a) {
        if (p.first >= last_end) {
            cnt++;
            last_end = p.second;
        }
    }
    cout << cnt << "\n";
    return 0;
}

時間複雜度：排序 O(n log n)，掃描 O(n) → 總計 O(n log n)

題目2 : Tasks and Deadlines

原題:
https://cses.fi/problemset/task/1630

題意：
每個任務有處理時間 t_i 與截止 d_i。定義獎勵 sum(d_i - C_i)，其中 C_i 是任務完成時刻。求最大獎勵。
等價於最小化 sum C_i（因 sum d_i 固定）。

解題思路:
要最小化所有任務完成時間總和，依處理時間 t_i 升序（Shortest Processing Time first）最優。
證明想法：任意相鄰兩任務若長的在前、短的在後，交換後可不劣，重複交換可排序成全短到長。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n; 
    cin >> n;
    vector<pair<int,int>> job(n);
    for (auto &p : job) cin >> p.first >> p.second;

    sort(job.begin(), job.end(), [](auto &a, auto &b){
        return a.first < b.first;
    });

    long long time = 0, reward = 0;
    for (auto &p : job) {
        time += p.first;
        reward += (long long)p.second - time;
    }
    cout << reward << "\n";
    return 0;
}

時間複雜度：O(n log n)

四、Leetcode實戰演練

題目1 : Jump Game

原題:
https://leetcode.com/problems/jump-game/description/

題意：
給長度 n 陣列 nums，nums[i] 代表從 i 最多能跳多遠。問能否從 0 跳到最後一格。

解題思路（貪心）:
維持目前能到達的最遠位置 far。掃描到 i 時，若 i ≤ far，可更新 far = max(far, i + nums[i])。
若過程中 far 已 ≥ n-1，即可回傳 true；若 i 超過 far，代表卡住回傳 false。

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int far = 0, n = nums.size();
        for (int i = 0; i<=far && i<n; i++) {
            far = max(far, i + nums[i]);
            if (far >= n - 1) return true;
        }
        return far >= n - 1;
    }
};

時間複雜度：O(n)

題目2 : Gas Station

原題:
https://leetcode.com/problems/gas-station/

題意：
有一圈加油站，第 i 站提供 gas[i] 油，開到下一站需 cost[i]。問從哪個起點能繞一圈（若有解唯一）。

解題思路（貪心）:

• 若總油量 sum(gas) < sum(cost)，一定無解。
• 單趟掃描維持當前油量 tank，從 start 出發。遇到 tank < 0，代表之前任何起點到這都會失敗，因此把 start 改成下一站、tank 歸零繼續；最後若總油量足夠，start 就是答案。

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int total = 0, tank = 0, start = 0;
        for (int i = 0; i < gas.size(); i++) {
            int diff = gas[i] - cost[i];
            total += diff;
            tank  += diff;
            if (tank < 0) {
                start = i + 1;
                tank = 0;
            }
        }
        return (total >= 0) ? start : -1;
    }
};

時間複雜度：O(n)

五、小結

• 區間類問題多半以結束時間排序可得最大可選集合。
• 想最小化完成時間總和 → 短工優先（SPT）。
• 線性可達性（能不能到終點）或資源平衡（油量差）常以維持一個最遠/餘量的變數，一次掃描解決。
• 記得：能用貪心通常可在「排序 + 一次遍歷」中完成，寫法簡潔、效率高。