Weighted Job Scheduling

1. The idea is to use recursion to reduce the big problem into several smaller subproblems.
2. The idea is to create an array of ‘Jobs’ of size N, where each entry of Jobs will have three elements: start time of the job, end time of the job and profit associated with the job.
3. Then, sort the Jobs array in increasing order of finish time.
4. Now, we will call a maxProfitHelper function that returns us the maximum profit obtained by performing the jobs. 
5. The algorithm for maxProfitHelper will be as follows:
   • maxProfitHelper(Jobs, current),  (where ‘Jobs’ is the sorted array of jobs, ‘current’ is the index of the current job of the Jobs array):
     • If current == 0:  return jobs[0].profit
     • Now, return the maximum of two profits:
       • maximum profit by excluding the current job.
       • maximum profit by including the current job.
6. In case of calculating profit by including current job, the idea is to find the latest job before the current job from sorted Jobs array, such that it does not conflict with Jobs[ current ] using another helper function nonConflicingJob() . Suppose the index of that job comes out to be i, then recursively call for maxProfitHelper(Jobs, i). Then total profit becomes profit from the recursive call + Jobs[ current ].profit.

We are solving this problem by solving its subproblems and then combining the solutions of those subproblems. If we analyze carefully, we will see that we are solving the same subproblems multiple times. Thus, this problem exhibits overlapping subproblems. This means, in this approach, we will eliminate the need for solving the same subproblems again and again. 

Let’s understand by an example:

Suppose the Job array after sorting is = [ {1, 2, 5}, {3, 4, 10}, {3, 6, 9}, {5, 7, 6}]. The recursion tree for this is:

As we can see:

• Job 2 is called 2 times.
• Job 1 is called 5 times.

To optimize the overlapping sub-problem calculation, we will use memoization by storing answers for each recursive state.

The idea is the same as the previous approach, but in the previous approach many recursive calls were made again and again with the same parameters. This can be eliminated by storing the value obtained from a particular call in a 1d array, called the lookUp array. lookUp[i] stores the maximum profit obtained by performing jobs till ith index.

Algorithm: 

• An array, lookUp, of size N is taken.
• Recursive Function: maxProfitHelper( Jobs, current, lookUp ), where ‘Jobs’ is the sorted array of jobs, ‘current’ is the index of the current job of the Jobs array. The initial call of this function will have current = N-1 as an argument.
• Base condition => current =  0 , return Jobs[0].profit
• If the value at lookUp[current] is not -1, use this value, that is, return it.
• There will be two cases:
  • Exclude the current job: In this case, we will not perform the current job and recursively call for maxProfitHelper( Jobs, current-1, lookUp).
  • Include the current job: In this case, we will find the latest non conflicting job before the Job[current] using another helper function nonConflictingJob(). And recursively call for maxProfitHelper(Jobs, inx, lookUp) where inx is the index of non conflicting job. The total profit, in this case, becomes profit from recursive call + Jobs[current].profit.
• The answer for this recursive function will be the maximum of the two profits.
• Update the maximum profit value in lookUp[current] for further use.

This approach relies on the fact that the maximum profit possible up to ith index is independent of the jobs coming after the ith index. Thus, for every index we will store the maximum profit from jobs upto that index in an array, say DP array. For every index there will be two cases :

• Include the current job: In this case, we will iterate over all jobs from i-1 to 0 and find the first non conflicting job with our current job i. The total profit, in this case, becomes profit from that conflicting job + profit from the ith job.
• Exclude the current job: In this case, our maximum profit is the answer of (i-1)th job.
• The maximum profit of ith job becomes the maximum of the two cases.

Algorithm: 

• Take a DP array of size ‘N’ and initialize all its values with 0.
• DP[0] = 1
• For every index ‘i’ of the Jobs array
  • Iterate over the indices for all ‘j’ such that i-1 >= j >= 0,  and if the job at index j is non conflicting with job at index i, DP[i] = max(DP[i], Job[i].profit +DP[j]). And then break the loop.
  • At the end of the above iteration, DP[i] = max(DP[i], DP[i-1]). DP[i-1] is the maximum profit by excluding the current job.
• Return the value of DP[N-1], that is the maximum profit till the last job.

1. An optimization of the previous approach is to use binary search as the jobs are sorted in increasing order of finish time.
2. We use binary search to find the latest non conflicting job before the current job.