 Solution

A greedy algorithm builds a feasible solution by repeatedly making the locally preferred available choice, committing to that choice without reconsidering earlier choices. “Preferred” must be specified by the problem's rule, such as choosing the cheapest eligible edge.

Local preference alone does not prove global optimality. A correctness argument needs a property ensuring that some optimum extends the choices already made, often proved by an exchange argument. Thus the distinguishing rule is