Answer:
Assumption: Only 1 job can be taken at a time
This becomes a weighted job scheduling problem.
Suppose there are n jobs
Sort the jobs according to fj(finish time)
Define an array named arr to store max profit till that job
arr[0] = v1(value of 1st job)
For i>0. arr[i] = maximum of arr[i-1] (profit till the previous job) or wi(weight of ith job) + profit till the previous non-conflicting job
Final ans = arr[n-1]
The previous non-conflicting job here means the last job with end timeless than equal to the current job.
To find the previous non-conflicting job if we traverse the array linearly Complexity(search = O(n)) = O(n.n) = O(n^2)
else if we use a binary search to find the job Complexity((search = O(Logn)) = O(n.Log(n))
