# Weighted Job Scheduling

You are given a list of jobs where each job has a start time, finish time, and the profit associated with that job, find the maximum profit subset of non-overlapping jobs.

**Problem description:**

The problem wants you to find the maximum profit that you can make after performing a certain number of jobs such that each job has a certain condition that you can start a job only if the start time of the current job is greater than the finish time of the previous job. You are required to develop some algorithm such that the job start time and the finish time does not coincide with other jobs.

**Input:**

The first line of the input consists of *T* number of test cases, each test case consists of *N* number of jobs, each for the following *N* lines consists of the start time, finish time and the profit for that job.

**Output:**

Print the maximum value of the profit that you can get after performing the given jobs in a separate lines.

**Examples:**

Input:
T=1
N=3
0 6 60
5 7 30
7 8 10
Output:
70,
as 0->6 and then 7->8 which in total gives 60 + 10 =70.
Input:
T=1
N=3
1 2 30
2 3 40
4 8 60
Output:
130,
as 1->2,2->3 and then 4->8 which in total gives (30+40+60).

1) Recursive Approach:In this approach we will use recursion, we will create a structure of job which will have three variable

st,enandprwhich will havestis equal to start,enis the end andprwill be profit.There are two possibilities for each job, either that job is included in the overall profit or otherwise, it is not included.

If that job is included in overall profit-making then we have to recur for those jobs which do not make any conflict with the selected job, so we make a find function which will take vector and index as a parameter and return the index of non-conflict job.

In order to find the index of the job index which do not make any intersection with the current selected job, we can also use a binary search method to reduce the time complexity.

The second possibility with the current job is that the selected job is not included in the overall profit.

Time Complexityfor the above approach in the worst case isexponentialSpace complexityfor the above approach isO(n)2) Dynamic Programming Approach:In this approach we will use memoization technique, we will create a dp[] state, each time we make a recursive call

we store that result in the

dp[]state, we will initialize alldp[]state with -1, if thedp[]is -1 then it means that has not been calculated so we need to calculate it and if it is not -1 then we will directly return it.Time Complexityfor the above approach in the worst case is:O(n*n)Space complexityfor the above approach in the worst case is:O(n)C++ Implementation (Recursive Approach):Output:C++ Implementation (Dynamic Programming Approach):

need an explanation for this answer? contact us directly to get an explanation for this answerOutput: