C: Shopping
問題
線分状のショッピングモールがある。
入口の座標は0、出口の座標はN+1、N個の店が座標1からNにある。
座標の移動には1単位時間かかる。入口から入って全ての店で買い物をして出口から出て行くのに、移動時間を最小化したい。
M個のルール(c[i], d[i])がある。
c[i], d[i]はc[i]<d[i]を満たしており、店c[i]より前に店dp[i]で買い物を指定なければならない。
解法
c[i] < d[i]なので入口からNまで行って、1まで戻りながら買い物し、
その後出口に行くと、1からNのどの区間も高々3回しか通らない。
またc[i]からd[i]の区間は必ず3回通る必要がある。
c[0] < d[0] < c[1] < d[1]のような場合d[0]からc[1]の区間は3回通る必要はなく1回だけで済む。
c[0] < c[1] < d[0] < d[1]ならc[0]からd[1]の区間は3回通る。
要は区間が重なっているならば、まとめて奥まで行って帰ってくる。
重なっていないならば別々に処理する。
c[i]でソートして区間をまとめる、もしくは3回通る区間を列挙して解く。
