When searching for a possible solution to a problem, we usually consider various solutions, which we call the solution space.

When trying to find the best solution to a problem, we're usually interested in a global optimum, that is, the optimal solution from the whole set of possible solutions.

However, the solution space can exhibit other optimums. Namely, we can have local optimums, which are optimal solutions in a small neighborhood of possible solutions.

The greedy choice property states that from a local optimum we can reach a global optimum, without having to reconsider decisions that have already been made.

In the activity selection problem for Peter, we applied the greedy choice by always choosing the activity with the earliest finish time from the set of available activities.

Intuitively, we can think that this problem exhibits the greedy choice property in the sense that if we have a maximum size subset and we replace the activity from that set with the earliest finish time with one that finishes even earlier, we are always left with a maximum size set, making it safe to always choose the one with the earliest finish time.

It is possible to prove that the greedy choice is always part of some optimal solution.

Let's try to prove that, for any nonempty subproblem S_k, if a_m is an activity in S_k with the earliest finish time, then a_m is included in some maximum size subset of mutually compatible activities of S_k.

To prove it, let's assume the following:

• A_k is a maximum size subset of mutually compatible activities in S_k
• a_j is the activity in A_k with the earliest finish time

If a_j = a_m, we are done. If a_j != a_m, we can try to replace a_j by am in A_k, producing the set A'_k = A_k - {a_k} ∪ {a_m}.

We can safely do that since the activities in A_k are disjoined. a_j is the first activity to finish in A_k, and f_m <= f_j.

Since |A'_k| = |A_k|, we conclude that A'_k is a maximum size subset of mutually compatible activities of S_k, and that it includes a_m.

Intuition usually helps us decide whether a greedy algorithm produces the optimal solution, without having to formally prove the optimal substructure and the greedy choice properties. We're also going to cover a different paradigm of algorithm design in this chapter, which is dynamic programming that also requires problems to exhibit the optimal substructure property. If you are not sure if a greedy algorithm works for a given problem due to the greedy choice, you can always build a dynamic programming solution for it to gain some insight.