Question

"Suppose that instead of always selecting the first activity to finish, we instead select the last activity to start that is compatible with all previously selected activities. De- scribe how this approach is a greedy algorithm, and prove that it yields an optimal solution."

Answer 1

Answer:

Explanation:

We can say according what we

already know that Greedy algorithm selects the shortest path, and we can also say that the given approach is greedy as it selects the last activity to start as it is the shortest path to take.

Now suppose we are given a set S = {x1, x2,..... , xn} (where x1, x2…. are activities), and xi = [si, fi), and we try to find an optimal solution by selecting the last activity to start that is compatible with all previously selected

activities.

Now create a set S’ = {x’1, x’2, · · · , x’n}, where x’i = [f’i, si). (x’1 = x1 in reverse). We can see that, a subset of {x1, x2, · · · , xn}⊂S is mutually compatible if and only if the corresponding subset {x’1, x’2, · · · , x’n} ⊂ S’ is also mutually compatible. Thus, an optimal solution for S maps directly to an

optimal solution for S’ and vice versa.

The given algorithm when run on S, produces the same result as the greedy algorithm when run on S’. The solution of algorithm for S corresponds to the solution of greedy algorithm for S’, and hence the algorithm is optimal.