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.
