optimal substructure for greedy

Suppose you have made one good decision and a smaller version of the same problem remains. Optimal substructure is the promise that solving that leftover problem optimally, and gluing it onto your first decision, gives an optimal solution to the whole thing. It is the property that lets a one-step-at-a-time method work at all: each step shrinks the problem to a smaller instance of the same kind.

Precisely: a problem has optimal substructure if an optimal solution is built from optimal solutions to its subproblems. For greedy specifically, you pair this with the greedy-choice property. The greedy-choice property says some optimal solution starts with the greedy choice; optimal substructure says that once that choice is fixed, what remains is a smaller instance whose own optimal solution completes the whole optimum. Together they justify induction: greedy is optimal on the subproblem (by the inductive hypothesis), the greedy first choice extends to a global optimum (greedy-choice), so greedy is optimal overall. For interval scheduling, after you pick the earliest-finishing job and delete everything that overlaps it, you are left with the very same problem on the remaining jobs.

This is the same optimal-substructure idea dynamic programming relies on — both paradigms need it. The difference is that greedy also needs the greedy-choice property, so it can commit to one subproblem instead of trying many. The caveat: many problems have optimal substructure but NOT the greedy-choice property; 0/1 knapsack is the classic case. Optimal substructure alone gets you dynamic programming; it does not by itself license greed.