c++实现带期限作业排序问题

带期限作业排序问题是一个经典的贪心问题，可以使用C++实现。具体实现步骤如下：

1. 创建作业结构体，包含作业编号、作业所需时间和截止时间两个属性。

struct Job {
    int jobId;          // 作业编号
    int timeNeeded;     // 作业所需时间
    int deadline;       // 截止时间
};

2. 创建一个比较函数，用于将作业按照截止时间从早到晚排序。

bool compare(Job a, Job b) {
    return a.deadline < b.deadline;
}

3. 将所有作业按照截止时间排序。

sort(jobs.begin(), jobs.end(), compare);

4. 创建一个布尔数组，表示每个时间点是否有作业在执行。

bool timeline[MAX];    // MAX为时间的最大值，根据实际情况确定

5. 从第一个作业开始遍历，将作业插入到最晚的可行时间点。

for (int i = 0; i < n; i++) {
    for (int j = min(MAX - 1, jobs[i].deadline) - 1; j >= 0; j--) {
        if (!timeline[j]) {
            timeline[j] = true;
            ans += jobs[i].timeNeeded;
            break;
        }
    }
}

6. 输出完成所有作业所需的最短时间。

cout << ans << endl;

完整代码如下：

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

const int MAX = 10005;

struct Job {
    int jobId;          // 作业编号
    int timeNeeded;     // 作业所需时间
    int deadline;       // 截止时间
};

bool compare(Job a, Job b) {
    return a.deadline < b.deadline;
}

int main() {
    int n;  // 作业数量
    cin >> n;
    vector<Job> jobs(n);
    for (int i = 0; i < n; i++) {
        jobs[i].jobId = i;
        cin >> jobs[i].timeNeeded >> jobs[i].deadline;
    }
    sort(jobs.begin(), jobs.end(), compare);
    bool timeline[MAX] = { false };
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = min(MAX - 1, jobs[i].deadline) - 1; j >= 0; j--) {
            if (!timeline[j]) {
                timeline[j] = true;
                ans += jobs[i].timeNeeded;
                break;
            }
        }
    }
    cout << ans << endl;
    return 0;
}