The first step in solving an optimization problem by using a greedy approach is to characterize the structure of an optimal solution. A problem exhibits the optimal substructure property if an optimal solution to the problem within it contains optimal solutions to subproblems.

Intuitively, we can think that the activity selection problem exhibits the optimal substructure property in the sense that, if we suppose that a given activity belongs to a maximum size set of mutually compatible activities, then we are left to choose the maximum size set of mutually compatible activities from the ones that finish before this activity starts and that start after this activity finishes. Those two sets must also be maximum sets for the compatible activities, so that they can showcase the optimal substructure of this problem.

Formally, it is possible to prove that the activity selection problem exhibits optimal substructure. Let's assume we have the set of activities sorted in monotonically increasing order of finish time so that the following can be true for activities i and j:

Whereas f_i is denoting the finish time of activity i.

Suppose we denote by S_ij; the set of activities that start after activity a_i finish, and they finish before activity a_j starts. Thus, we wish to find a maximum set of mutually compatible activities in S_ij.

Let's say that the set is A_ij, and includes activity a_k. By including a_k in an optimal solution, we are left with two subproblems that are finding the maximum subset of mutually compatible activities in the set S_ik and set S_kj, which can be represented as follows:

Thus, the size of the maximum size set of mutually compatible activities in S_ij is given by the following:

If we could find a set A'_kj of mutually compatible activities in S_kj where |A'_kj| > |A_kj|, then we could use A'_kj instead of A_kj in the optimal solution to the subproblem for S_ij. But that way, we would have something that contradicts the assumption that A_ij is an optimal solution: