Determine Maximum Profit Algorithm C++：带截止期限订单调度最大利润求解

这是经典的带截止日期的单机调度最大化收益问题，采用贪心算法即可得到最优解，步骤如下：

• 所有订单按利润从高到低降序排列，优先处理利润更高的订单
• 维护一个数组记录每周是否已被占用，初始状态所有周均未被占用
• 遍历排序后的订单，对当前订单，从它的截止周开始向前找第一个未被占用的周：
  • 找到则将该周标记为已占用，将当前订单利润计入总利润
  • 没找到则直接放弃当前订单

你之前两种思路出错原因：

1. 按周遍历仅选当周截止的最高利润订单：会错过截止时间更晚但利润更高的订单，导致高利润订单最后没有空余时间槽可用
2. 按利润降序但优先安排更早时间槽：会浪费早的时间槽，导致后续截止时间更早的高利润订单无槽可放，正确逻辑是给当前订单安排尽可能晚的可用时间槽，预留更早槽位给其他截止时间更早的订单

按利润降序排序后订单顺序为：订单1(截止3周，利润40)、订单2(截止1周，利润35)、订单3(截止1周，利润30)、订单4(截止3周，利润25)、订单5(截止1周，利润20)、订单6(截止3周，利润15)、订单7(截止2周，利润10)

1. 处理订单1：截止3周，最晚可用槽是3周，占用后总利润40
2. 处理订单2：截止1周，最晚可用槽是1周，占用后总利润75
3. 处理订单3：截止1周无可用槽，放弃
4. 处理订单4：截止3周向前找，2周可用，占用后总利润100
5. 剩余订单均无可用槽，最终总利润和样例输出一致。

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

// 订单结构体
struct Order {
    int id;
    int deadline;
    int profit;
};

// 排序规则：利润降序
bool cmp(const Order& a, const Order& b) {
    return a.profit > b.profit;
}

int main() {
    int n;
    while (cin >> n && n != 0) {
        vector<Order> orders(n);
        int max_deadline = 0;
        for (int i = 0; i < n; i++) {
            cin >> orders[i].id >> orders[i].deadline >> orders[i].profit;
            if (orders[i].deadline > max_deadline) {
                max_deadline = orders[i].deadline;
            }
        }
        // 最多n个订单，截止时间超过n的话最多也只能安排n个，优化空间
        max_deadline = min(max_deadline, n);
        vector<bool> slot(max_deadline + 1, false); // 下标从1开始对应第1周
        int total_profit = 0;
        // 按利润降序排序
        sort(orders.begin(), orders.end(), cmp);
        for (int i = 0; i < n; i++) {
            // 从截止周往前找可用槽
            for (int j = min(orders[i].deadline, max_deadline); j >= 1; j--) {
                if (!slot[j]) {
                    slot[j] = true;
                    total_profit += orders[i].profit;
                    break;
                }
            }
        }
        cout << total_profit << endl;
    }
    return 0;
}

内容的提问来源于stack exchange，提问作者ParkerHarrelson123