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

Problem of the day

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.

```
The start time of one job can be equal to the end time of another.
```

Detailed explanation

```
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.
```

```
2
4
1 2 3 3
3 4 5 6
50 10 40 70
3
1 1 1
5 3 4
5 6 4
```

```
120
6
```

```
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.
```

```
2
4
1 3 6 2
2 5 9 100
50 20 100 200
2
1 2
2 3
10 20
```

```
250
30
```