1235. Maximum Profit in Job Scheduling

yPhantom 2019年10月20日 81次浏览

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, you need to output the maximum profit you can take such that there are no 2 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:

img

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:

img

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:

img

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

Solution

给定每项任务的开始时间和结束时间以及收益,求组合起来不越界的最大收益。

典型动态规划题目。

我们简历两个dp的ArrayList,分别是dpEndTime和dpProfit。

dpEndTime记录每次能得到最大收益时对应的结束时间。

dpProfit记录每次能得到的最大收益是多少。

上述两个数组一一对应。

对于某项工作k而言,首先在dpEndTime中找到k.startTime + 1之前能得到最大收益的结束时间对应的下标,用来去dpProfit取最大收益。完成一个dp更新过程。

代码如下:

class Solution {
    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int[][] items = new int[startTime.length][3];
        for (int i = 0; i < startTime.length; i++) {
            items[i] = new int[]{startTime[i], endTime[i], profit[i]};
        }
        Arrays.sort(items, (a1, a2) -> a1[1] - a2[1]);
        List<Integer> dpEndTime = new ArrayList<>();
        List<Integer> dpProfit = new ArrayList<>();
        
        // 初始化,避免越界
        dpEndTime.add(0);
        dpProfit.add(0);

        for (int[] item: items) {
            int s = item[0];
            int e = item[1];
            int p = item[2];
            int preIndex = Collections.binarySearch(dpEndTime, s + 1);
            if (preIndex < 0) {
                preIndex = -preIndex - 1;
            }
            preIndex--;
            int currentProfit = dpProfit.get(preIndex) + p;
            int maxProfit = dpProfit.get(dpProfit.size() - 1);
            if (currentProfit > maxProfit) {
                dpProfit.add(currentProfit);
                dpEndTime.add(e);
            }
        }
        return dpProfit.get(dpProfit.size() - 1);
    }
}