Weighted Job Scheduling

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
32 upvotes
Asked in companies
MeeshoGoogleGoldman Sachs

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1:
2
4
1 2 3 3
3 4 5 6
50 10 40 70
3
1 1 1
5 3 4
5 6 4
Sample Output 1:
120
6
Explanation for Input 1:
For test case 1:
We perform the jobs in this order for maximum profit: 1 -> 4.
So the total profit becomes 50 + 70 = 120.

For test case 2:
As all the jobs are overlapping, we can perform only one job. Therefore we perform the job with maximum profit i.e. the 2nd one. Thus, the total profit is 6.
Sample Input 2:
2
4
1 3 6 2
2 5 9 100
50 20 100 200
2
1 2 
2 3 
10 20
Sample Output 2:
250
30
Hint

Try all possible ways of doing the jobs and maximize the answer among the valid ones.

Approaches (4)
Brute Force
  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.
Time Complexity

O(N * (2^N)) per test case, where N is the number of jobs.

 

In the worst case, we are sorting the Jobs array which takes O(N*logN) time. For each Job we have 2 choices either to include it or not, this leads to time complexity of (2.2.2..N terms), and also at each step we are finding the nonconflicting job which takes O(N) time in the worst case. So, the overall time complexity becomes O(N*logN) + O(N)*O( 2^N) = O(N*(2^N)).

Space Complexity

O(N) per test case, where N is the number of jobs.

 

In the worst case, we are creating a Job array of size N which takes O(N) space. Also, we are using recursion. So O(N) space will be taken by recursion stack. Thus the overall space complexity is O(2*N) or O(N).

Code Solution
(100% EXP penalty)
Weighted Job Scheduling
Full screen
Console