ABC127 C Prison

問題は「$ N個の区間が与えられる. それらを重ねたとき, $ N重になっている要素は何個あるか？」というものに帰着できる.

この問題は一種の典型で, 区間の左端と右端に分けて考えることで, 左端の最大値を$ a, 右端の最小値を$ bとおくと, 答えは$ max(0, b - a + 1)となる. よって最大値・最小値を順次更新していくことによって, $ O(N)でこの問題を解くことができた.