Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Weighted Job Scheduling

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
28 upvotes
Asked in companies
AtlassianGrowwIntuit

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 )
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
Full screen
Console