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

The given problem is a generalization of the Activity Selection Problem where we need to find a set of non-conflicting activities with maximum weight. This can be solved using a dynamic programming approach.

Step-by-step explanation:

The given problem is a generalization of the Activity Selection Problem. In this problem, we are given a set of activities, each with a start time, finish time, and weight. The goal is to find a set of non-conflicting activities with maximum weight.

To solve this problem using dynamic programming, we can define a table where each entry represents the maximum weight that can be achieved up to a particular activity index. We iterate through the activities in a top-down manner and update the table based on the maximum weight we can achieve by including or excluding the current activity.

By considering the start and finish times of the activities and comparing them with other activities, we can determine which activities are non-conflicting. We can then compute the weight for each non-conflicting activity and find the set with the maximum weight.

Answer 2

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