1235. Maximum Profit in Job Scheduling

09/19/2021

Leetcode

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 * 104

• 1 <= startTime[i] < endTime[i] <= 109

• 1 <= profit[i] <= 104

Basic Idea

我们注意到，对于每个task我们可以选择schedule或者跳过，如果我们选择schedule，则只能在它的endtime之后考虑之后start的其他task，这里是可能会有重复计算的。事实上我们可以在对tasks的start time排序之后，利用cache来存放每个start时间对应的之后所有tasks能获得的最大profit，这样可以把时间复杂度降低到 O(NlogN), 因为一开始的排序和每次的二分。

1. DFS with Memoization: 利用递归的思路从第一个任务开始，每次尝试schedule或者skip，利用二分法来找到某个时间点之后start的第一个task

2. DP using TreeMap: 利用TreeMap作为DP，从最后一个开始的task开始，每次检查当前task的profit以及它结束之后开的的tasks中能获得的最大profit之和，以及如果skip当前task所能获得的最大profit

java Code:

// DFS with memoization
class Solution {
    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        Map<Integer, Integer> cache = new HashMap<>();
        int[][] tasks = new int[startTime.length][3];
        for (int i = 0; i < startTime.length; ++i) {
            tasks[i] = new int[] {startTime[i], endTime[i], profit[i]};
        }
        Arrays.sort(tasks, (t1, t2) -> {
            if (t1[0] != t2[0]) return Integer.compare(t1[0], t2[0]);
            else return Integer.compare(t2[1], t1[1]); // 结束晚的在前
        });
        return getMaxProfitStartFrom(tasks[0][0], tasks, cache);
    }
    
    private int getMaxProfitStartFrom(int start, int[][] tasks, Map<Integer, Integer> cache) {
        int nextIndex = searchNextStartTaskIndex(start, tasks);
        if (nextIndex == -1) {
            return 0;
        }
        int[] task = tasks[nextIndex];
        if (cache.containsKey(task[0])) {
            return cache.get(task[0]);
        }
        // 分别考虑schedule相同start time的所有task
        int maxProfit = 0;
        for (int i = nextIndex; i < tasks.length; ++i) {
            if (i > nextIndex && tasks[i][0] != task[0]) {
                break;
            }
            maxProfit = Math.max(maxProfit, 
                tasks[i][2] + getMaxProfitStartFrom(tasks[i][1], tasks, cache));
        }
        // 考虑 skip 当前start time的所有task
        maxProfit = Math.max(maxProfit, getMaxProfitStartFrom(task[0] + 1, tasks, cache));
        cache.put(task[0], maxProfit);
        return maxProfit;
    }
    
    // 找到开始时间>= start的第一个task的index, return -1 if not found
    private int searchNextStartTaskIndex(int start, int[][] tasks) {
        int left = 0, right = tasks.length - 1;
        while (left + 1 < right) {
            int mid = (left + right) / 2;
            if (tasks[mid][0] < start) {
                left = mid;
            } else {
                right = mid;
            }
        }
        if (tasks[left][0] >= start) return left;
        else if (tasks[right][0] >= start) return right;
        else return -1;
    }
}

//DP:
class Solution {
    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int N = startTime.length;
        TreeMap<Integer, Integer> dp = new TreeMap<>();
        int[][] tasks = new int[N][3];
        for (int i = 0; i < N; ++i) {
            tasks[i] = new int[] {startTime[i], endTime[i], profit[i]};
        }
        Arrays.sort(tasks, (t1, t2) -> Integer.compare(t1[0], t2[0]));
        for (int i = tasks.length - 1; i >= 0; --i) {
            int[] task = tasks[i];
            int start = task[0], end = task[1], p = task[2];
            Map.Entry<Integer, Integer> entryAfterEnd = dp.ceilingEntry(end);
            int val = entryAfterEnd == null ? p : p + entryAfterEnd.getValue();
            Map.Entry<Integer, Integer> entryAfterStart = dp.firstEntry();
            if (entryAfterStart != null && entryAfterStart.getValue() > val) {
                dp.put(start, entryAfterStart.getValue());
            } else {
                dp.put(start, val);
            }
        }
        return dp.firstEntry().getValue();
    }
}