[leetcode 周赛 159] 1235 规划兼职工作

1235 Maximum Profit in Job Scheduling 规划兼职工作

问题描述

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

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

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

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

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

示例 1:

[leetcode 周赛 159] 1235 规划兼职工作

输入: 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:

[leetcode 周赛 159] 1235 规划兼职工作

输入: 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:

[leetcode 周赛 159] 1235 规划兼职工作

输入: 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

思路

  • 读题
    在endTime的时间内, 工作获得最大收益, 工作有一时间段, 可能有空闲时间段(该时间段没有工作)
    注意空闲时间没有工作, 但工作的收益是有后效性的 即时间i的收益为p 那么时间i+1即使没有工作, 收益也为p

动态规划

在某时间i内, 获得最大值, dp[i]

  1. 在任意的时间点i, dp[i] = max(dp[i-1], dp[i]) 它等于前一段时间的最大收益
  2. 在工作结尾的时间点i, dp[i] = max(dp[s] + profit, dp[i]) 它等于接收这份工作[s, i] 总收益加上工作收益

[leetcode 周赛 159] 1235 规划兼职工作

  • 样例: startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60]
// 工作结尾时间点=[工作索引列表]
{9=[4], 10=[2], 3=[0], 5=[1], 6=[3]}
// dp变化
[1, 2, 3, 4,  5,  6,  7,  8,  9, 10,  11]

[0, 0, 0, 0,  0,  0,  0,  0,  0,  0,   0]   [end:1  cur:0]
[0, 0, 0, 0,  0,  0,  0,  0,  0,  0,   0]   [end:2  cur:0]
[0, 0, 0, 20, 0,  0,  0,  0,  0,  0,   0]   [end:3  cur:20]
[0, 0, 0, 20, 20, 0,  0,  0,  0,  0,   0]   [end:4  cur:20]
[0, 0, 0, 20, 20, 20, 0,  0,  0,  0,   0]   [end:5  cur:20]
[0, 0, 0, 20, 20, 20, 90, 0,  0,  0,   0]   [end:6  cur:90]
[0, 0, 0, 20, 20, 20, 90, 90, 0,  0,   0]   [end:7  cur:90]
[0, 0, 0, 20, 20, 20, 90, 90, 90, 0,   0]   [end:8  cur:90]
[0, 0, 0, 20, 20, 20, 90, 90, 90, 150, 0]   [end:9  cur:150]
[0, 0, 0, 20, 20, 20, 90, 90, 90, 150, 150] [end:10 cur:150]

代码实现

动态规划

public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
    int len = startTime.length;
    // <工作结束时间, 工作索引列表> etc:工作结束时间为5的工作列表为[0, 2, 3] {5=[0,2,3]}
    Map<Integer, List<Integer>> endMap = new HashMap<>(len);
    // 工作最晚结束时间(dp数组的长度)
    int maxEndTime = 0;
    for (int i = 0; i < len; i++) {
        List<Integer> idxList = endMap.getOrDefault(endTime[i], new ArrayList<>());
        idxList.add(i);
        endMap.put(endTime[i], idxList);
        maxEndTime = maxEndTime < endTime[i] ? endTime[i] : maxEndTime;
    }
    System.out.println(endMap);

    // dp[i] 时间i以内 工作收获最大值
    int[] dp = new int[maxEndTime + 1];
    for (int end = 1; end <= maxEndTime; end++) {
        // 如果遍历的时间是某份工作的结尾时间 那么比对其开始时间能获得的最大收益
        if (endMap.containsKey(end)) {
            for (Integer oth : endMap.get(end)) {
                dp[end] = Math.max(dp[startTime[oth]] + profit[oth], dp[end]);
            }
        }
        // 时间end以内最大值 是自身和其前一时间(因为这段时间可能是空闲时间--没有一份工作是落在这时间段)
        // 主要用来使得dp[s] 不会因为空闲时间而无收益 
        // 工作的收益是有后效性的 即时间i的收益为p 那么时间i+1即使没有工作, 收益也为p
        dp[end] = Math.max(dp[end - 1], dp[end]);
        System.out.println(Arrays.toString(dp) + "\t[end:" + end + " cur:" + dp[end] + "]");
    }

    return dp[maxEndTime];
}

参考资源

第 159 场周赛 全球排名

上一篇:LeetCode 159 Longest Substring with At Most Two Distinct Characters


下一篇:写给程序员的机器学习入门 (二) - pytorch 与矩阵计算入门