1235. Maximum Profit in Job Scheduling

Difficulty: Hard

Related Topics: Binary Search, Dynamic Programming, Sort

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⁴

• 1 <= startTime[i] < endTime[i] <= 10⁹

• 1 <= profit[i] <= 10⁴

Solution

Language: Java

class Solution {
    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        List<Task> tasks = new ArrayList<>();
        HashMap<Integer, Integer> invertIndex = new HashMap<>();
        int[] dp = new int[profit.length];
        int maxEnd = 0;
        for (int i = 0; i < startTime.length; i ++) {
            Task temp = new Task(startTime[i], endTime[i], profit[i]);
            tasks.add(temp);
            maxEnd = Math.max(maxEnd, endTime[i]);
        }
        tasks.sort(new Comparator<>() {
            public int compare(Task a, Task b) {
                return a.end - b.end;
            }
        });
        
        for (int i = 0; i < tasks.size(); i++) {
            invertIndex.put(tasks.get(i).end, i);
        }
        
        dp[0] = tasks.get(0).profit;
        
        for (int i = 1; i < tasks.size(); i++) {
            dp[i] = Math.max(tasks.get(i).profit, dp[i - 1]);
            for (int j = i - 1; j >= 0; j--) {
                if (tasks.get(j).end <= tasks.get(i).start) {
                    dp[i] = Math.max(dp[i], tasks.get(i).profit + dp[j]);
                    break;
                }
            }
        }
        
        int max = 0;
        
        for (int i = 0; i < dp.length; i ++) {
            max = Math.max(max, dp[i]);
        }
        
        return max;
        
        
    }
}
​
​
class Task {
    int start;
    int end;
    int profit;
    
    Task(int start, int end, int profit) {
        this.start = start;
        this.end = end;
        this.profit = profit;
    }
}