N個の区間(開始Si 終了Ti)がある。共通部分がないようになるべく多くの区間を選びたい。
この時最も早い終了の区間()を順に選んでいく貪欲法が最適解をもたらすことが知られている。
なぜか？
- 最初の一つの区間を選ぶ
- 区間が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個選ぶことができる
http://www.prefield.com/algorithm/misc/interval_scheduling.html