= Greedy-choice property
A <greedy-choice property> says that some optimal <feasible solution> contains the locally selected choice. Together with <optimal substructure> in the remaining instance, it allows repeated commitments. An <exchange argument> often establishes this property.<Algorithms by Jeff Erickson/Greedy Algorithms>[Algorithms by Jeff Erickson; §4.3 General Pattern, printed pp. 164–165: exchange without worsening an optimum]{ref}
For <interval scheduling>, a safe first choice need not belong to every optimal <feasible solution>. When several optima exist, a commitment may exclude one while retaining another. The useful <loop invariant> is that the accepted prefix can still be extended to an optimum. Merely keeping the accepted <intervals> compatible proves feasibility, which is a weaker claim.
Back to article page
