How the 2 properties we just discussed Interact in Greedy Algorithms ?
In greedy algorithms:
The greedy choice property ensures that each choice you make as you solve the problem is safe—i.e., this choice will not prevent you from achieving the optimal solution.
Optimal substructure in the context of greedy algorithms means that after making a greedy choice, the remaining problem (which is a subproblem) should still have the property that making a series of optimal local choices within it leads to an optimal solution for that subproblem.
To put it another way, the greedy choice property is about the safety and efficacy of making each individual choice without considering the entire problem, whereas optimal substructure ensures that after making one of these choices, the smaller leftover problem is itself optimally solvable by continuing to make such greedy choices.
Consider the activity selection problem again:
Greedy Choice: Always select the next activity that starts after the last selected activity ends and ends the soonest. This is based on the greedy choice property, suggesting that choosing the shortest immediate option will contribute correctly to the global solution.
Optimal Substructure: Once an activity is selected, the problem reduces to selecting activities from those that start after the chosen activity ends. The optimal substructure property assures us that solving this reduced problem optimally (by continuing to make greedy choices) will give us an optimal solution for the reduced scope, which together with the previously made choices, composes an optimal solution for the entire problem.