Consider the following three alternative approaches, also greedy, for the proble

ID: 3543113 • Letter: C

Question

Consider the following three alternative approaches, also greedy, for the problem. In each case, the same

process used to select the next activity greedily, is repeated until no more activities can be

selected.

(a) Select an activity of least duration that is compatible with the currently chosen ones.

(b) Select an activity that overlaps with fewest other remaining activities and is compatible

with the currently chosen ones.

compatible with the currently chosen ones.

For all the above approaches, prove or disprove (with a counter-example) that the algorithm

gives an optimal solution.

A)First activity ------------ (1,10)

Second Activity --------(9,12)

Third Activity ------------(11,17)

If least duration is considered we can select only activity 2;

but optimallly we can select 1st and 3rd both

b)First activity ------------ (1,10)

Second Activity --------(9,15)

Third Activity ------------(12,18)

Fourth activity ----------(20,25)

If we consider least overlaps we consider only 4th activity as it has 0 overlaps but

optimally we can select 1st,2nd and 4th

c)First activity ------------ (1,100)

Second Activity --------(9,12)

Third Activity ------------(14,17)

If we caonsiderearliest start time we select only 1st but

optimally we can select both 2nd and 3rd

Best solution:

Sort the activites according to finish times and select which has least finish time and compatible with the alread selected ones