UVALive 2757：貪心選擇任務最大獎金

問題描述

有 n 個任務，每個任務有獎金 p_i 和截止時間 d_i。每個任務耗時 1，同一時間只能做一個任務。選擇任務子集使所有任務在截止時間前完成，最大化總獎金。

解題思路

經典貪心：按截止時間升序排序。從最後時間倒推，每個時間點選擇獎金最大且未被選且截止時間 ≥ 當前時間的任務。實現：排序後，維護一個最大堆（優先隊列）存放可用任務獎金。從最大截止時間遞減到 1，將截止時間 ≥ 當前時間的任務加入堆，取堆頂累加獎金。

代碼實現 (C++)

#include 
using namespace std;
struct Task { int p, d; };
int main() {
    int n;
    while (cin >> n) {
        vector tasks(n);
        for (int i = 0; i < n; ++i) cin >> tasks[i].p >> tasks[i].d;
        sort(tasks.begin(), tasks.end(), [](Task a, Task b){ return a.d < b.d; });
        priority_queue pq;
        long long ans = 0;
        int idx = n - 1;
        for (int t = tasks.back().d; t >= 1; --t) {
            while (idx >= 0 && tasks[idx].d >= t) {
                pq.push(tasks[idx].p);
                --idx;
            }
            if (!pq.empty()) {
                ans += pq.top(); pq.pop();
            }
        }
        cout << ans << endl;
    }
    return 0;
}

複雜度分析

• 時間複雜度：O(n log n)（排序 + 堆操作）。
• 空間複雜度：O(n)。

總結

任務調度貪心經典模型：按截止時間倒序，每個時隙選最大利潤任務。優先隊列完美支持「可用任務集合」的動態維護。