>先進性を示す。任意の"時点"で最適な方法であることを、"時系列"順に示す。

> 最適解に仮定できる性質を課していく（2つ入れ替えても悪くならないのでこの形etc）と、貪欲になることを示す

>･各操作において最適たりうる選択(その選択を含む最適解が存在するという意味)を行う

> ･各操作の後にはより規模の小さい問題に帰着でき、再帰的に解が求まる

> ･証明は基本的に背理法で、最適解が全て「貪欲による選択」を含まないと仮定して矛盾を示す

>ex.)区間スケジューリング

> 時刻0で示す。I= [L,R] をRが最小なものの1つとし、全ての最適解がIを含まないと仮定する。最適解の1つを取り(最適解が存在することは明らか)、そのうちRが最小なものをJ= [L',R'] とすると、Jは必ずIと置き換えられることで矛盾。従ってIを採用してよい。

>こうすると、貪欲の証明でよく目にする「損をしない」というフレーズが出てこない。