 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.^[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.