Question

Consider the following generalization of the Activity Selection Problem: You are given a set of n activities each with a start time si , a finish time fi , and a weight wi . Design a dynamic programming algorithm to find the weight of a set of non-conflicting activities with maximum weight.

Answer 1

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