ABC127 C Prison
問題は「
$ N
個の区間が与えられる. それらを重ねたとき,
$ N
重になっている要素は何個あるか?」というものに帰着できる.
この問題は一種の典型で, 区間の左端と右端に分けて考えることで, 左端の最大値を
$ a
, 右端の最小値を
$ b
とおくと, 答えは
$ max(0, b - a + 1)
となる. よって最大値・最小値を順次更新していくことによって,
$ O(N)
でこの問題を解くことができた.
実装例:
https://atcoder.jp/contests/abc127/submissions/19916055