Weighted Job Scheduling

Posted: 15 Jan, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

You are given 'N' jobs with their start time 'Start', end time 'End' and profit 'Profit'. You need to tell the maximum profit you can obtain by performing these jobs such that no two jobs overlap.

Note:
The start time of one job can be equal to the end time of another.
Input Format:
The first line contains an integer 'T' denoting the number of test cases to be run. 

The first line of each test case contains a single integers 'N' denoting the number of jobs. 

The second line of each test case contains ‘N’ single space-separated integers denoting the start time of 'N' jobs respectively.

The third line of each test case contains ‘N’ single space-separated integers denoting the end time of 'N' jobs respectively.

The fourth line of each test case contains ‘N’ single space-separated integers denoting the profit of 'N' jobs respectively.
Output Format:
For each test case, the maximum profit is printed.

Print the output of each test case in a separate line.
Follow up :
Can you solve this problem in O(N*log(N)) time complexity?
Constraints:
1 <= T <= 100
1 <= N <= 3000
1 <= Start[i] < End[i] <= 10^9
1 <= Profit[i] <= 10^9

Where 'T' denotes the number of test cases, 'N' denotes the number of jobs respectively, 'Start[i]' and 'End[i]' denotes the start and end time of  'i-th' job, and 'Profit[i]' denotes the profit of  'i-th' job. 
Approach 1
  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.
Try Problem