きままにものづくり

日々の気付いたことなんかを書いてます。

SRM645Div1Easy

問題

一年の間にN人の客がある宿に泊まりに来る。N人の滞在期間を表すarrivalsとdeparturesの二つの配列
が与えられる。宿主は特別なプロモーションを特定の人にかけることで、その人からよい評価をえることができる。また、プロモーションをかけられた人のと出会った人も、宿に対してよい評価を持つ。N人からよい評価をもらうためには、最小で何人にプロモーションをかけたら良いのか計算せよ。

解法

departureを昇順にソートする。よい評価を得ていない最小のdepartureの客を選ぶ。その客と同じ期間、滞在する人の中でdepartureが最大の客を選び、その人を選択する。これを全員からよい評価を得るまで繰り返す。

計算量

O(N^2)

コード

広告を非表示にする