ferinの競プロ帳

競プロについてのメモ

区間系の問題

区間[l,r]がいっぱいとんできて条件を満たすように区間を選ぶときの数の最大(最小)を求めるみたいなやつ とりあえず終点でソート

区間スケジューリング問題

Spaghetti Source - 区間スケジューリング
終点が早い区間から選んでいくのが最適解になることを示す

  • 任意の最適解を選ぶ
  • その解のうち一番はやく終わる区間を全体でもっとも早く終わるものに置き換える
  • この操作を行ったとしても仕事の数は変化しないので最適解であるのは変わっていない
  • 同様に二番目に終わる区間を選べるうちでもっとも早く終わる区間に置き換えると操作を行っていく
  • この操作を繰り返すと終了時間が早いものから貪欲に取っていく解が構成される

メモ Kの重複を許す区間スケジューリング問題 - buyoh.hateblo.jp

SRM645

区間の終点でソートするとうまくいく
SRM 645 div1 easy JanuszTheBusinessman - ferinの競プロ帳

CODE FESTIVAL 2017 Final D - Zabuton

D - Zabuton
[h, h+p]の区間がいっぱいあると考えると終点h+pでソートすると最善になっている