区間スケジューリング
N個の区間(開始Si 終了Ti)がある。共通部分がないようになるべく多くの区間を選びたい。
この時最も早い終了の区間($ \argmin_i T_i)を順に選んでいく貪欲法が最適解をもたらすことが知られている。 なぜか？
最初の一つの区間を選ぶ
区間が1つ以上あるなら、そこから1つ選ぶことができる。
「最後に選んだ区間の終了」をFと呼ぶことにする。
最も早い終了の区間を選ぶ選び方は1個の可能な選び方のうち最もFが小さい。(Fmin_1とする)
Fより前に開始のある区間は今後選択不能である。
選んだ区間と交差するから。
既にk個の区間が選ばれており、k+1番目を選ぶことを考える。
Fより後に開始のある区間が1つ以上ある時、そこから1つ選ぶことができる。
あるF > Fmin_kで1つ選ぶことができるならF = Fmin_kでも一つ選ぶことができる。
その選ばれてるものを選べばよいから。
Fmin_kより後に開始のある区間から最も早い終了の区間を選ぶ
これはk+1個の可能な選び方のうち最もFが小さい。(Fmin_{k+1}とする)
数学的帰納法によりn個の区間を選ぶ方法があるなら、この方法でn個選ぶことができる