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

Last Updated: 15 Jan, 2021

Moderate

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

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

```
For each test case, the maximum profit is printed.
Print the output of each test case in a separate line.
```

```
Can you solve this problem in O(N*log(N)) time complexity?
```

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

- The idea is to use recursion to reduce the big problem into several smaller subproblems.
- 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. - Then, sort the
**Jobs**array in increasing order of finish time. - Now, we will call a
**maxProfitHelper**function that returns us the**maximum profit obtained by performing the jobs.** - 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.

- maxProfitHelper(Jobs, current), (where ‘Jobs’ is the sorted array of jobs, ‘current’ is the index of the current job of the Jobs array):
- 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.

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.

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

Similar problems

Ninja And The Strictly Increasing Array

Moderate

Posted: 27 Nov, 2022

Negative To The End

Easy

Posted: 16 Dec, 2022

Sort 0s, 1s, 2s

Easy

Posted: 24 Dec, 2022

Day 28 : Fake Coin Problem

Easy

Posted: 24 Dec, 2022

Day 28 : Fake Coin Problem

Easy

Posted: 24 Dec, 2022

Find Duplicate in Array

Easy

Posted: 5 Jun, 2023