KUPC2012 D.権力

問題

N個の部屋が1直線上に並んでおり、外からの侵略者が各部屋を狙っている。
侵略者から部屋を守りたい。
ある人は、ある区間をまとめて守ることができ、人と守れる区間のリストが与えられる。
できるだけ少ない人数で守る時、その人数を答える。
全ての部屋を守れないときはImpossibleを返す。

考え方

各部屋をノードと考えて、ある区間i〜jを守る時、iからi+1、iからi+2、、、iからj、iからj+1までコスト1の辺をはる。
1の部屋から(仮想的な)N+1の部屋まで最小コストで移動したものが、答えになる。

反省

1をカバーできるもので、一番広くカバーできるものを選ぶ。
カバーできてない範囲で一番小さい番号の部屋をカバーできるもので、一番広くカバーできるものを選ぶ。
上記を繰り返す貪欲法で解ける。