貪欲法は、その時点で最善に見える選択を確定させ、後から見直すことはありません。通常は並べ替えと1回の走査だけなので高速ですが、局所的な選択が最終的な答えを悪くしないと論証できる場合にしか正しくなりません。
よく使う論証は交換です:任意の最適解を取り、その選択の1つを貪欲な選択に入れ替えて、答えが悪くならないことを示します。最も安い品物を先に買っても品物の数が減らないなら、安い順に買うのは安全です。拠点iでの失敗がそれより前のすべての拠点を候補から外すなら、iの次からやり直すのは安全です。
貪欲法の問題は、自然な順序(最も安い、終了が最も早い、差が最も小さい)と、後の選択肢を狭めない選択があることで見分けてください。前の選択が後のより良い組み合わせを妨げうる場合は疑ってください:変則的な額面の硬貨体系や価値付きのナップサックは、貪欲法が失敗し動的計画法が必要になる典型例です。面接では、コードを書く前に交換論法を声に出して説明してください。