贪心算法截止日期问题C++代码

以下是一个简单的贪心算法截止日期问题的C++代码示例：

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

struct Task {
    int id, deadline, profit;
};

bool cmp(Task a, Task b) {
    return a.profit > b.profit; // 按照利润从大到小排序
}

void scheduleTasks(vector<Task>& tasks) {
    sort(tasks.begin(), tasks.end(), cmp);
    int n = tasks.size();
    vector<int> slot(n, -1);
    int profit = 0;
    for(int i=0; i<n; i++) {
        for(int j=min(n, tasks[i].deadline)-1; j>=0; j--) {
            if(slot[j] == -1) { // 如果该时间点可用
                slot[j] = tasks[i].id; // 安排该任务
                profit += tasks[i].profit; // 计算利润
                break;
            }
        }
    }
    cout << "最大利润：" << profit << endl;
    cout << "安排的任务：";
    for(int i=0; i<n; i++) {
        if(slot[i] != -1) {
            cout << slot[i] << " ";
        }
    }
    cout << endl;
}

int main() {
    int n;
    cout << "输入任务个数：" << endl;
    cin >> n;
    vector<Task> tasks(n);
    cout << "输入每个任务的截止日期和利润：" << endl;
    for(int i=0; i<n; i++) {
        tasks[i].id = i+1;
        cin >> tasks[i].deadline >> tasks[i].profit;
    }
    scheduleTasks(tasks);
    return 0;
}

该代码使用了一个结构体 `Task` 来表示每个任务的属性，其中包括任务编号、截止日期和利润。通过自定义比较函数 `cmp` 将任务按照利润从大到小排序。然后，使用一个 `vector` 来表示每个时间点是否被占用，初始化为 -1 表示该时间点可用。接着，从前往后遍历任务列表，对于每个任务，从该任务的截止日期开始往前找，找到第一个可用时间点，并将该任务安排在该时间点。最后，计算总利润和输出安排的任务列表。

注意，该代码中贪心策略是按照利润从大到小排序，优先安排利润高的任务。如果有多个任务的利润相同，则安排截止日期早的任务。这种贪心策略可能不是最优的，但可以得到一个近似最优解。