考えたこと

与えられたパスをなるべく少ない回数でカットしたい

あるカットを1つ選んだ時に、それで切れるパスを全部取り除いて、残りについて考える時に、先程のカットは影響しない

ということは「一番端のパスを含んでなるべく多くのパスを切るカット」をグリーディに選んでいけば良いのでは

それで良いのか、良いことの証明は？

公式解説

僕の方法では「aでソートして一番小さいもののb-1を切る」

公式解説では「bでソートして一番小さいもののb-1を切る」

どういう違いがあるか？

bでソートして一番小さいものがaでも小さい時には差はない

そうでない時

なるほど確かに公式の方が正しい

区間スケジューリングの貪欲アルゴリズムによく似ている