Weighted Job Scheduling
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

Question

Weighted Job Scheduling

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.

Accepted Answer

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.

To optimise it further we can 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.

Accepted Answer

Brute Force

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

Space Complexity: O(n)Explanation:

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

Time Complexity: O(2^n)Explanation:

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

Accepted Answer

Recursive Memoization

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.

Let’s understand by an example:

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.

Space Complexity: O(n)Explanation:

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 and a lookUp array of size N, which also takes O(N) space. Also we are using recursion, so O(N) space will be taken by recursion stack O(N). So the overall complexity becomes O(N) + O(N) + O(N) = O(3*N) or O(N).

Time Complexity: O(n^2)Explanation:

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

In the worst case, we are sorting the Jobs array which takes O(N*log(N)) time, and also we will be filling the lookup table of size N which takes O(N) time and at every step, we are calling nonConflictingJob() which takes O(N) time to find the latest nonconflicting job. So Overall time complexity becomes O(N^2)+ O(N*log(N)) = O(N^2).

Accepted Answer

Bottom Up DP

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.

Space Complexity: O(n)Explanation:

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 and DP array of size N. Hence, the overall space complexity is O(N).

Time Complexity: O(n^2)Explanation:

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

In the worst case, we are sorting the jobs array of size N which takes O(N*log(N)) time, and then we will be filling the DP array of size N which takes O(N) time. And for filling each DP[i] we are taking O(N) time to find the nonconflicting job. So, the overall time complexity becomes O(N^2) + O(N*log(N)) = O(N^2).

Accepted Answer

Using Binary Search

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.

Space Complexity: O(n)Explanation:

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 and DP array of size N. Hence, the overall space complexity is O(N).

Time Complexity: O(nlogn)Explanation:

O(N*log(N)) per test case, where N is the number of Jobs.

In the worst case, we are sorting the Jobs array of size N, which takes O(N*log(N)) time, and then we will be again filling the DP table of size N, which takes O(N) time. But now for filling each DP[i] we are taking O(logN) time to find the nonconflicting job. So, the overall complexity becomes O(N*log(N)).

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:

Input Format:

Output Format:

Follow up :

Constraints:

Top PhonePe Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in PhonePe Software Developer