1235.maximum-profit-in-job-scheduling.md

你打算利用空闲时间来做兼职工作赚些零花钱。

这里有  n  份兼职工作，每份工作预计从  startTime[i]  开始到  endTime[i]  结束，报酬为  profit[i]。

给你一份兼职工作表，包含开始时间  startTime，结束时间  endTime  和预计报酬  profit  三个数组，请你计算并返回可以获得的最大报酬。

注意，时间上出现重叠的 2 份工作不能同时进行。

如果你选择的工作在时间  X  结束，那么你可以立刻进行在时间  X  开始的下一份工作。

---

解题思路

区分动态规划类型，此题为划分型动态规划，

dp[i]表示到时间 i 所能获得的最大收益

struct Node {
    int start;
    int end;
    int profit;

    Node(int _s, int _e, int _p) : start(_s), end(_e), profit(_p) {};

    friend bool operator<(const Node &n1, const Node &n2) {
        if (n1.end == n2.end) return n1.start > n2.start;
        return n1.end > n2.end;
    }
};

class Solution {
public:
    int jobScheduling(vector<int> &startTime, vector<int> &endTime, vector<int> &profit) {
        int n = startTime.size();
        priority_queue<Node> q;
        int m = 0;
        for (int i = 0; i < n; i++) {
            q.push({startTime[i], endTime[i], profit[i]});
            m = max(m, endTime[i]);
        }
        vector<int> dp(m + 1, 0);
        for (int i = 1; !q.empty() && i <= q.top().end; ) {
            if (i < q.top().end) {
                dp[i+1] = dp[i];
                i++;
                continue;
            }

            auto t = q.top();
            q.pop();
            dp[t.end] = max(dp[t.end], dp[t.start] + t.profit);
        }
        return dp[m];
    }
};

---

follow up

如果有 N 个兼职人员，可以获取的最大报酬？

---

相似题目

N 个出租车订单 start_time[N], end_time[N], profit[N], 我有一辆出租车，能获得的最大利润是多少？

follow up: 假如有 n 辆出租车接单，能获取的最大利润是多少？