SRM645Div1Easy
問題
一年の間にN人の客がある宿に泊まりに来る。N人の滞在期間を表すarrivalsとdeparturesの二つの配列
が与えられる。宿主は特別なプロモーションを特定の人にかけることで、その人からよい評価をえることができる。また、プロモーションをかけられた人のと出会った人も、宿に対してよい評価を持つ。N人からよい評価をもらうためには、最小で何人にプロモーションをかけたら良いのか計算せよ。
解法
departureを昇順にソートする。よい評価を得ていない最小のdepartureの客を選ぶ。その客と同じ期間、滞在する人の中でdepartureが最大の客を選び、その人を選択する。これを全員からよい評価を得るまで繰り返す。
計算量
