perogram

D. TV Shows 〜multisetのlowerbound〜

Quiz

https://codeforces.com/contest/1061/problem/D

AC Code

https://codeforces.com/contest/1061/submission/56465574

解法

  • showの開始順にソート
  • 空いているTVがあり、それを使った方が「新規に借りるよりも得」の場合は再利用する
  • その時、空いているTVのうち後端が1番大きいものを選ぶ

注意点

  • サンプルを見れば分かるが、[1, 2]と[2, 3]は連結できない

Note

f:id:peroon:20190703175421j:plain

感想

  • 現在考えているShowの「開始」時刻をキーとして、
  • すでに借りているTVたちの「終了」時刻のうち最後のものを検索する必要があり、
  • 構造体のmultisetのlowerboundを使ったりして中々大変だったが、乗り越えられて良かった