How does Greedy Choice work for Activities sorted according to finish time?

Let the given set of activities be S = {1, 2, 3, …n}, and activities are sorted by finish time. The greedy choice is to always pick activity 1. How come activity 1 always provides one of the optimal solutions?

 We can prove it by showing that if there is another solution B with the first activity other than 1, then there is also a solution A of the same size as activity 1 as the first activity. Let the first activity selected by B be k, then there always exist A = {B – {k}} U {1}.

Note: The activities in B are independent and k has the smallest finishing time among all. Since k is not 1, finish(k) >= finish(1))

Greedy is an algorithmic paradigm that builds up a solution piece by piece, always choosing the next piece that offers the most obvious and immediate benefit. Greedy algorithms are used for optimization problems. 

An optimization problem can be solved using Greedy if the problem has the following property: 

• At every step, we can make a choice that looks best at the moment, and we get the optimal solution to the complete problem. 

If a Greedy Algorithm can solve a problem, then it generally becomes the best method to solve that problem as the Greedy algorithms are in general more efficient than other techniques like Dynamic Programming. But Greedy algorithms cannot always be applied. For example, the Fractional Knapsack problem can be solved using Greedy, but 0-1 Knapsack cannot be solved using Greedy.