leetcode weekly contest 159 周赛 5233. 规划兼职工作 1235. Maximum Profit in Job Scheduling

目录

1. 解答

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

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

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

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

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

示例 1：

输入：startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]
输出：120
解释：
我们选出第 1 份和第 4 份工作， 
时间范围是 [1-3]+[3-6]，共获得报酬 120 = 50 + 70。

示例 2：

输入：startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60]
输出：150
解释：
我们选择第 1，4，5 份工作。 
共获得报酬 150 = 20 + 70 + 60。

示例 3：

输入：startTime = [1,1,1], endTime = [2,3,4], profit = [5,6,4]
输出：6

提示：

• 1 <= startTime.length == endTime.length == profit.length <= 5 * 10^4
• 1 <= startTime[i] < endTime[i] <= 10^9
• 1 <= profit[i] <= 10^4

解答

做到这个题的时候只有 10 分钟了。我考虑这个题目应该是转化为图。开始时间最小的点先作为一个源点（入度为 0），在它结束之前开始的点按照时间时间先后作为它的下一个节点，有一条有向边。但是需要剔除哪些开始时间在这个点的所有下一个节点中结束时间最早的那个时间之后的点。按照这个方法递归操作。剩下再选入度为 0 的点做源点，继续操作，只到遍历了所有入度为 0 的点。然后再以所有入度为 0 的点分别开始，找权值最大路径。

稍后我写一下，补上。

感觉我的想法是不行的。

看了中国榜第十名 9am 的做法，用的 Javascript，是很巧妙的动规。我又用 python 实现了一下。后面也附上了 9am 的代码。

class Solution:
    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
        el = []
        for i in range(len(startTime)):
            el.append([startTime[i], endTime[i], profit[i]])
        el.sort(key=lambda x:x[1])
        dp = []
        for i in range(len(el)):
            l = 0
            r = i - 1
            while l < r:
                m = int((l + r) / 2 + 0.5)
                if el[m][1] > el[i][0]:
                    r = m - 1
                else:
                    l = m
            if l == 0 and el[l][1] > el[i][0]:
                dp.append(el[i][2])
            else:
                dp.append(dp[l] + el[i][2])
            if i > 0 and dp[i] < dp[i-1]:
                dp[i] = dp[i-1]
        return dp[-1]

思路是先按照结束时间排好序，数组为 el，dp[i] 就是只看前 i 个的最大收益，dp[0]，肯定是第一个工作的收益，第 i 个的受益是前面所有里面，结束时间比第 i 个开始时间早的最靠后的一个的下标记为 l，如果 l 存在，dp[i] = max(dp[i-1], dp[l] + el[i][2])，如果 l 不存在，dp[i] = max(dp[i-1], )

/**
 * @param {number[]} startTime
 * @param {number[]} endTime
 * @param {number[]} profit
 * @return {number}
 */
var jobScheduling = function(startTime, endTime, profit) {
    let temp = [];
    for (let i = 0; i < startTime.length; i++) {
        temp.push({ s: startTime[i], e: endTime[i], p: profit[i] });
    }
    temp = temp.sort((a,b) => (a.e-b.e));
    const result = [];
    for (let i = 0; i < temp.length; i++) {
        let l = 0;
        let r = i - 1;
        while (l < r) {
            const m = Math.round((l + r) / 2);
            if (temp[m].e > temp[i].s) {
                r = m - 1;
            } else {
                l = m;
            }
        }
        if (l === 0 && temp[l].e > temp[i].s) {
            result.push(temp[i].p);
        } else {
            result.push(temp[i].p + result[l]);
        }
        if (i > 0 && result[i] < result[i - 1]) {
            result[i] = result[i-1];
        }
    }
    return result[temp.length - 1];
};