区間スケジューリング問題
複数の区間が与えられ、それぞれの始点と終点がわかっている。区間が互いに重ならないようにできるだけたくさん区間をとりたい。最大いくつの区間がとれるか、という問題。
これは貪欲法でよく出てくる問題で競プロでも形を変えて出てくる。ポイントは区間を終点の早い順に並べ、順に採用していくというもの。そのときにいま見ている区間の始点が最後に採用した区間の終点以降であれば、その区間を採用し、そうでなければ採用しない、ということを繰り返すと最適になる。 きちんと証明するのはやや面倒だが、まず