SRM645 div1 250
問題
ホテルにN人泊りに来る。
i番目の人は、arr[i]日に到着し、dep[i]日に出発する。
ある人にプロモーション活動をすると、その人のレビューはGOOD判定になる。
さらに、プロモーション活動した人が滞在中にホテルに滞在した人(到着日、出発日を含む)もGOOD判定になる。
最低何人にプロモーション活動すれば、すべての人のレビューがGOOD判定になるか?
考え方
Greedy解
出発日が早い順にソート。
一番出発が早い人のレビューをGOODにするためには、その人かその人と滞在がかぶる人にプロモーションしないといけない。
さらに、その中でも出発日が遅ければ遅い人を選べば、レビューがGOODになる人が増える。
そのような人を選んで、まだレビューがGOODになっていない、一番出発が早い人に同様に処理すれば、最少人数がわかる。