1235.规划兼职工作

链接：1235.规划兼职工作
难度：Hard
标签：数组、二分查找、动态规划、排序
简介：给你一份兼职工作表，包含开始时间 startTime，结束时间 endTime 和预计报酬 profit 三个数组，请你计算并返回可以获得的最大报酬。

题解 1 - cpp

• 编辑时间：2022-10-22
• 执行用时：252ms
• 内存消耗：64.1MB
• 编程语言：cpp
• 解法介绍：dp 存储当前点选中和不选中两种情况，利用 map 快速查找当前节点启动前结束的最大值。

struct Node { int l, r, profit; };
class Solution {
public:
    map<int, int> m;
    int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
        int n = startTime.size();
        vector<Node> list(n);
        for (int i = 0; i < n; i++) {
            list[i].l = startTime[i];
            list[i].r = endTime[i];
            list[i].profit = profit[i];
        }
        sort(list.begin(), list.end(), [](Node &a, Node &b){ return a.r < b.r; });
        vector<vector<int>> dp(n, vector<int>(2, 0));
        dp[0][1] = list[0].profit;
        m[list[0].r] = list[0].profit;
        for (int i = 1; i < n; i++) {
            dp[i][1] += list[i].profit;
            dp[i][0] = max(dp[i][0], dp[i - 1][0]);
            dp[i][0] = max(dp[i][0], dp[i - 1][1]);
            auto upper = m.upper_bound(list[i].l);
            upper--;
            if (upper->first <= list[i].l) dp[i][1] = upper->second + list[i].profit;
            m[list[i].r] = max(m[list[i].r], max(dp[i][0], dp[i][1]));
        }
        return max(dp[n - 1][0], dp[n - 1][1]);
    }
};

题解 2 - python

• 编辑时间：2024-05-04
• 执行用时：195ms
• 内存消耗：34.35MB
• 编程语言：python
• 解法介绍：记录当前开始时间以前结束的收益最高的任务。

class Solution:
    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
        n = len(startTime)
        arr = sorted([i for i in range(n)], key = lambda i: startTime[i])
        q = []
        wait_q = []
        dp = [profit[arr[i]] for i in range(n)]
        for i in range(0, n):
            idx = arr[i]
            while wait_q and wait_q[0][0] <= startTime[idx]:
                wait_idx = heappop(wait_q)[1]
                heappush(q, (-dp[wait_idx], wait_idx))
            if q: dp[i] += -q[0][0]
            heappush(wait_q, (endTime[idx], i))
        return max(dp)