hey can you provide me answer to this questionPlease Answer

hey can you provide me answer to this question.Please Answer it step by step

Consider a weighted form of the activity selection problem of CLRS3 section 16.1 in which each of the n activities is weighted by its importance (the weight is unrelated to the starting and finishing times and to the duration). We want to choose a subset of non-conflicting activities with the highest total weight. Prove that the heuristic of choosing the earliest finishing time does not always result in an optimal schedule. Give an 0(n^2) algorithm to compute an optimal schedule.

Solution

(a) Prove that the heuristic of choosing the earliest finishing time does not always result in an optimal schedule.

Solution: The Greedy algorithm for Earliest finish time activity scheduling is :

Step 1: Arrange the activities in their increasing order of their finish time.

Step 2: Store the starting time of activity in an array say S.

Step 3: Always select first activity. Let finish time be f .

Step 4: Iterate over S to find the first index i such that S[i] f .

Consider the following activities say A1, A2, A3 and A4 with their start and end times as

A1 (1, 10) A2 (2, 5) A3 (4, 9) A4 (5, 12)

Now according to earliest finish time scheduling method, A2 is chosen as first activity as it has the smallest finish time among all the four activities. Now next activity chosen is A4 because its starting time is greater than or equal to A2\'s finishing time (5>=5). Next A3 is chosen and finally A1 is scheduled.

But this solution is not optimal as A2 takes 3 (5-2) to complete hence A3 can be chosen next, followed by A5 and finally ending with A1.

Hence proved that earliest finish time (EFT) does not always result in an optimal schedule.

(b) Give an O(n^2) algorithm to compute an optimal schedule

//Algorithm: To compute optimal schedule

//Input: an Array of n activities with start time (s) and finish time (f)

//Output: Order of scheduling activities.

Sort the activities in the increasing order of their finishing time.

A[] = {a1, a2, a3, ...an} array of all n activities.

F[] ={f1, f2, f3, ..., fn} where f1<=f2<=f3.....<=fn

Put all the corresponding start time in an array S.

S[] ={s1, s2, s3, ...sn} where si corresponds to F[].

i=0;

while(A is not empty)

{

for(j=1; j<n; j++)

{ //If the start time is greater than or equal to finish time of previously selected activity then chose this activity

// as next activity

if(s[j]>=f[i])

{

i = j;

Remove ai from array A and put ai in output array.

}

}

}