[LeetCode][Hard]Maximum Profit in Job Scheduling 规划兼职工作 | Java

问题

Maximum Profit in Job SchedulingHard

We have n jobs, where every job is scheduled to be done from startTime[i] to endTime[i], obtaining a profit of profit[i].

You're given the startTime, endTime and profit arrays, return the maximum profit you can take such that there are no two jobs in the subset with overlapping time range.

If you choose a job that ends at time X you will be able to start another job that starts at time X.

 

Example 1:

Input: startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]
Output: 120
Explanation: The subset chosen is the first and fourth job. 
Time range [1-3]+[3-6] , we get profit of 120 = 50 + 70.

Example 2:

Input: startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60]
Output: 150
Explanation: The subset chosen is the first, fourth and fifth job. 
Profit obtained 150 = 20 + 70 + 60.

Example 3:

Input: startTime = [1,1,1], endTime = [2,3,4], profit = [5,6,4]
Output: 6

 

Constraints:

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

解题思路

在进行工作规划时，只要时间不冲突，可行的工作规划有很多，本题要求找出获利最大的一种。这是一个寻找最优子结构的问题，遇到这类问题，一般就会想到大名鼎鼎的动态规划 （Dynamic programming）。动态规划的思想就是把一个问题分解为几个子问题，利用递归求解子问题，推出最终的解。通常会把子问题的解保存下来，用于后续的推导，以避免重复计算。

动态规划解法的重中之重就是列出状态转移方程，例如  dp(n+1)=dp(n)+1 dp(n+1) = dp(n) + 1 dp(n+1)=dp(n)+1 。本题要求从给定的工作中找出最大的获利，我们定义dp(n)dp(n)dp(n)为从时间点n以后开始的工作中，可以获得的最大利益。那么对于一个开始结束时间为s,e，工资为p的工作job（s,e,p）job（s,e,p）job（s,e,p），它的状态转移方程可以表示为dp(s)=p+dp(e)dp(s) = p + dp(e)dp(s)=p+dp(e)。由于从s开始的工作可能存在多个，那么最终的状态转移方程就是dp(s)=max(pi+dp(ei))dp(s) = max(p_i + dp(e_i))dp(s)=max(pi​+dp(ei​))

动态规划一般有两种写法，可以写成自顶向下（Top-down DP），或者自底向上（Bottom-up DP）。本文将给出Bottom-up的写法，小伙伴们可以自行脑补一下Top-down的写法。为了方便寻找某个工作结束后的下一个工作，我们需要将所有的工作按照开始时间排序。另外，我们采用了Bottom-up的写法，需要从开始时间最晚的工作开始处理，开始时间较晚的处理结果可能在后续的计算中，被开始时间较早的工作使用到。

参考答案

public class Solution {

    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        // convert 3 arrays to one 2D array for sorting
        int[][] jobs = new int[startTime.length][3];
        for (int i = 0; i < startTime.length; i++) {
            jobs[i] = new int[]{startTime[i], endTime[i], profit[i]};
        }
        // sort all jobs by startTime
        Arrays.sort(jobs,Comparator.comparingInt(a -> a[0]));
        // dp[i] stands for the max profit starts from jobs[i]
        int[] dp = new int[jobs.length];
        dp[jobs.length - 1] = jobs[jobs.length - 1][2];
        // calculate from the end to start
        // to make sure that the dp[next] of next job has been calculated
        for (int cur = jobs.length - 2; cur >= 0; cur--) {
            int next = findNext(cur, jobs);
            dp[cur] = Math.max(
                jobs[cur][2] + (next == -1 ? 0 : dp[next]),
                dp[cur + 1]
            );
        }
        return dp[0];
    }

    private int findNext(int cur, int[][] jobs) {
        for (int next = cur + 1; next < jobs.length; next++) {
            // the startTime of next job should be later than the endTime of current job
            if (jobs[next][0] >= jobs[cur][1]) {
                return next;
            }
        }
        return -1;
    }
}

拓展训练

来看看其他的动画规划问题吧！

或者到作者的LeetCode专栏中看看，有没有其他感兴趣的问题吧！

资料链接

原题 leetcode.com/problems/ma…