1235. Maximum Profit in Job Scheduling – Solution – Java

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
  

Solution

1. Sort jobs by starting time
2. For each position either job will be choosen or can be skipped.
   • If at a position job is choosen to be executed, we can’t execute any other job until this job ends. So next job we can find which starts at or after this job’s end time.
   • If we’re skipping this job, we can execute next job directly.
3. We have to find out maximum profit for each position.
4. To reduce recalculation, we will be storing result of max profit for each position.
5. Once we reach to last position, now we can return final answer as profit.

class Solution {    
    
    int[] memo;

    class Job{
        public int startTime;
        public int endTime;
        public int profit;
        
        public Job(int startTime,int endTime, int profit){
            this.startTime = startTime;
            this.endTime = endTime;
            this.profit = profit;
        }
    }
    
    // finding next non-conflicting job using binary search
    private int findNextJob(List<Job> jobs, int lastEndingTime) {
        int start = 0, end = jobs.size() - 1, nextIndex = jobs.size();
        
        while (start <= end) {
            int mid = (start + end) / 2;
            if (jobs.get(mid).startTime >= lastEndingTime) {
                nextIndex = mid;
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        return nextIndex;
    }
    
    private int findMaxProfit(List<Job> jobs, int n, int position) {
        // end of iteration
        if (position == n) {
            return 0;
        }
        
        // already calculated max profit for position
        if (memo[position] != -1) {
            return memo[position];
        }
        
        // binary search for finding next non conflicting job
        int nextIndex = findNextJob(jobs, jobs.get(position).endTime);
        
        // find the maximum profit of our two options: skipping or scheduling the current job
        int maxProfit = Math.max(findMaxProfit(jobs, n, position + 1), 
                        jobs.get(position).profit + findMaxProfit(jobs, n, nextIndex));
        
        // return maximum profit and also store it for future reference (memoization)
        return memo[position] = maxProfit;
    }
    
    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int length = startTime.length;
        memo = new int[length];
        
        Arrays.fill(memo, -1);

        List<Job> jobs = new ArrayList<>(startTime.length);
        
        for(int i=0;i<length;i++){
            jobs.add(new Job(startTime[i],endTime[i],profit[i]));
        }
        
        jobs.sort(Comparator.comparingInt(a -> a.startTime));
        
        // starting with 0th index
        return findMaxProfit(jobs, length, 0);
        
    }
}

Complexity Analysis

Let N be the length of the jobs array.

Time complexity: O(N logN)

Sorting jobs according to their starting time will take O(NlogN).

The time complexity for the recursion (with memoization) is equal to the number of times findMaxProfit is called times the average time of findMaxProfit. The number of calls to findMaxProfit is 2∗N because each non-memoized call will call findMaxProfit twice. Each memoized call will take O(1) time while for the non-memoized call, we will perform a binary search that takes O(logN) time, hence the time complexity will be O(N logN + N).

The total time complexity is therefore equal to O(NlogN).

Space complexity: O(N)

Storing the jobs N space. Hence the complexity is O(N).

The space complexity of the sorting algorithm depends on the implementation of each programming language. For instance, in Java, the Arrays.sort() for primitives is implemented as a variant of quicksort algorithm whose space complexity is O(logN). Thus the use of the inbuilt sort() function adds O(logN) to space complexity.

The result for each position will be stored in a memo and the position can have values from 00 to NN, thus the space required is O(N). Also, stack space in recursion is equal to the maximum number of active functions. In the scenario where every job is not scheduled, the function call stack will be of size N.

The total space complexity is therefore equal to O(N).