一、學習目標

• 分辨何時用 貪心（依結束時間排序）、何時用 DP（帶權區間排程）。
• 熟悉帶權區間 DP：排序、預處理 prev（相容區間）、二分查找轉移。
• 能將「多資源（k 條機器/影廳）」類問題用 貪心 + multiset 解最優解。
• 整理可套用的模板：
  • 帶權區間 DP：dp[i]=max(dp[i-1], dp[prev[i]]+w[i])
  • 無權最大場次：結束時間最早優先（活動選擇）

二、觀念說明

• 無權區間（最大可選數量）：選「最早結束」→ 經典貪心正確。
• 帶權區間（收益不同）：單純貪心不保證最優，改用 DP + 二分。
• DP 狀態：將區間依結束時間排序，dp[i] 表示考慮到第 i 個區間（取或不取）的最佳收益。
• 轉移：
  • 不取 i：dp[i] = dp[i-1]
  • 取 i：dp[i] = dp[prev[i]] + w[i]（prev[i] 為與 i 不重疊的最後一個區間索引）
• 多機器/多人同時進行（如 CSES Movie Festival II）：
  • 仍按結束時間排序，維護一個 multiset（或平衡樹） 存目前每台機器的「最後結束時間」。
  • 對每個新區間 [s,e]，找到 ≤ s 的最大結束時間機器接續；若沒有且仍有空機器，新增一台；否則略過。

三、CSES實戰演練

題目1:Projects

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

題意：
給 n 個專案，每個專案 [a,b] 完成可得利潤 p，任兩個被選專案不可重疊。求最大總利潤。

解題思路：

• 依結束時間 b 排序
• 預處理 prev[i]：最後一個 b < a[i] 的索引（用 upper_bound）
• 轉移 dp[i] = max(dp[i-1], dp[prev[i]] + p[i])

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

struct Job { long long a,b,p; };

int main(){
    int n; 
    cin>>n;
    vector<Job> v(n);
    for(int i=0;i<n;i++) cin>>v[i].a>>v[i].b>>v[i].p;
    sort(v.begin(), v.end(), [](const Job& x, const Job& y){ return x.b < y.b; });

    vector<long long> ends(n);
    for(int i=0;i<n;i++) ends[i] = v[i].b;

    auto find_prev = [&](int i){ // 最大 j < i 使得 ends[j] < v[i].a
        int j = upper_bound(ends.begin(), ends.end(), v[i].a - 1) - ends.begin() - 1;
        return j; // -1 表示沒有
    };

    vector<long long> dp(n+1, 0); // dp[0]=0，對應使用 0 個工作
    for(int i=1;i<=n;i++){
        int j = find_prev(i-1) + 1; // 轉成 dp 的索引（+1）
        dp[i] = max(dp[i-1], dp[j] + v[i-1].p);
    }
    cout << dp[n] << "\n";
    return 0;
}

題目2:Movie Festival II

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

題意：
n 部電影，每部 [s,e]，最多有 k 個人同時看（每人同時只能看一部且不可重疊）。求能看的最大總場次。

解題思路：

• 依結束時間排序
• 維護 multiset ms 為當前每個人的「最後結束時間」
• 對每部電影找 it = ms.upper_bound(s)；
  • 若 it == ms.begin()：表示沒有任何人能接這場，若 ms.size() < k 就新增一人看（insert(e)），否則略過；
  • 否則 --it（找到 ≤ s 的最大結束時間），把它換成 e（erase(it); insert(e)），答案 +1。

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n, k;
    cin>>n>>k;
    vector<pair<long long,long long>> mv(n);
    for(int i=0;i<n;i++) cin>>mv[i].first>>mv[i].second; // s, e
    sort(mv.begin(), mv.end(), [](auto &x, auto &y){ return x.second < y.second; });

    multiset<long long> ms; // 每個人的最後結束時間
    long long ans = 0;
    for(auto &[s,e]: mv){
        auto it = ms.upper_bound(s);
        if(it == ms.begin()){
            if((int)ms.size() < k){
                ms.insert(e);
                ans++;
            } // 否則：無法安排
        }else{
            --it; // 使用能接續的那位
            ms.erase(it);
            ms.insert(e);
            ans++;
        }
    }
    cout << ans << "\n";
    return 0;
}

四、Leetcode實戰演練

題目1:Maximum Profit in Job Scheduling

原題:
https://leetcode.com/problems/maximum-profit-in-job-scheduling/description/

題意：
與 CSES Projects 相同。

解題思路：
將 startTime/endTime/profit 打包成工作，依結束時間排序，二分 prev，做 DP。

class Solution {
public:
    int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
        int n = startTime.size();
        struct Job{int s,e,p;};
        vector<Job> v(n);
        for(int i=0;i<n;i++) v[i] = {startTime[i], endTime[i], profit[i]};
        sort(v.begin(), v.end(), [](const Job& a, const Job& b){ return a.e < b.e; });

        vector<int> ends(n);
        for(int i=0;i<n;i++) ends[i] = v[i].e;

        auto prev_idx = [&](int i){
            int j = upper_bound(ends.begin(), ends.end(), v[i].s - 1) - ends.begin() - 1;
            return j;
        };

        vector<long long> dp(n+1, 0);
        for(int i=1;i<=n;i++){
            int j = prev_idx(i-1) + 1;
            dp[i] = max(dp[i-1], dp[j] + v[i-1].p);
        }
        return dp[n];
    }
};

題目2:Non-overlapping Intervals

原題:
https://leetcode.com/problems/non-overlapping-intervals/

題意：
刪除最少區間使得其餘區間互不重疊。

解題思路：
選最多不重疊區間（結束時間最早優先），答案 = n - 選到的數量。

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if(intervals.empty()) return 0;
        sort(intervals.begin(), intervals.end(), [](auto& a, auto& b){
            if(a[1] != b[1]) return a[1] < b[1];
            return a[0] < b[0];
        });
        int cnt = 0, lastEnd = INT_MIN;
        for(auto &it: intervals){
            if(it[0] >= lastEnd){
                cnt++;
                lastEnd = it[1];
            }
        }
        return (int)intervals.size() - cnt;
    }
};