Problem Description

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

Solution

We first sort tasks by its start time.

The first idea is DP. The base case is when there is one task. And to generalize the solution, suppose we know the solution for tasks i+1,i+2,...,n. That is, dp[i+1] is the max profit we can have starting from the time startTime[i+1]. How could we build the solution dp[i]? Note that there are two situations to consider: either we take the task i, or we do not take task i. In the latter case, the max profit is just dp[i+1]. In the first case where we take the task i, we need to scan through task i+1, i+2,...,n to see if task i ends before the start time of them. Suppose task j is the first task which starts after task i, the max profit is simply dp[j] + profit[i]. Finally we take the larger value between dp[j] + profit[i] and dp[i+1].

The second idea is that we compute max profit dp[i], where dp[i] means the max profit we can have starting from time 0 and the task i must be taken. When we have all dp, we simply pick the max value among them. Now, given tasks 1,2,...,i-1, and we ask what is the max profit we can have by requiring taking task i? We need to find all task chains (connected tasks) that ends before startTime[i] and choose the one with max profit. To optimize the performance, at task i, we check the best task chain ending before startTime[i] and record the max profit as maxprofit, and remove those chains. (Note that those chains are safe to remove since they can not have the max profit for the original problem.) At the next iteration task i+1, we then only check chains with ending time between startTime[i] and startTime[i+1], and compare with maxprofit and take the largest one, which would be the max profit we can have before time startTime[i+1]. To realize these operations, we need to have a way to sort by endTime of chains dynamically. We can use min heap. In addition, we do not need to store the connected chains, only profit (and end time of course) associated with that chain would be enough.

Code

DP

class Solution {
    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int nTasks = startTime.length;
        int[][] task = new int[nTasks][3];

        for(int i=0; i< nTasks; i++) {
            task[i][0] = startTime[i];
            task[i][1] = endTime[i];
            task[i][2] = profit[i];
        }
        Arrays.sort( task, (a,b)->Integer.compare(a[0],b[0]) );

        int[] dp = new int[nTasks];
        for( int start=nTasks-1; start>=0; start-- ) {
            dp[start] = task[start][2];
            int next = findNextJob( task[start][1], task, start+1, nTasks-1 );
            if( next>0 ) dp[start] += dp[next];
            dp[start] = Math.max( dp[start], start+1<nTasks ? dp[start+1] : 0 );
        }

        return dp[0];
    }

    private int findNextJob( int endtime, int[][] task, int l, int r ) {
        while(l <= r){
            int mid = (l+r) / 2;
            if( task[mid][0]<endtime ) l = mid+1;
            else{
                if( task[mid-1][0] >= endtime ) r = mid-1;
                else return mid;
            }
        }
        return -1;
    }
}

Min Heap

class Solution {

    class comp implements Comparator<ArrayList<Integer>> {
        public int compare( ArrayList<Integer> l1, ArrayList<Integer> l2 ){
            return l1.get(0) - l2.get(0);
        }
    }

    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
       int nTasks = startTime.length;
        int[][] task = new int[nTasks][3];

        for(int i=0; i< nTasks; i++) {
            task[i][0] = startTime[i];
            task[i][1] = endTime[i];
            task[i][2] = profit[i];
        }
        Arrays.sort( task, (a,b)->Integer.compare(a[0],b[0]) );

        return findMaxProfit( task );
    }

    private int findMaxProfit( int[][] task ){
        PriorityQueue<ArrayList<Integer>> pq = new PriorityQueue<>(new comp());

        int maxprofit = 0;
        int len = task.length;

        for( int i=0; i<len; i++ ){
            while( !pq.isEmpty() && pq.peek().get(0) <= task[i][0] ){
                maxprofit = Math.max( maxprofit, pq.peek().get(1) );
                pq.poll();
            }

            pq.add( new ArrayList<Integer>( List.of(task[i][1], maxprofit+task[i][2]) ) );
        }

        while( !pq.isEmpty() ){
            maxprofit = Math.max( maxprofit, pq.peek().get(1) );
            pq.poll();
        }

        return maxprofit;

    }

}