Intersection [AtCoder Beginner Contest 199（Sponsored by Panasonic） B]

https://atcoder.jp/contests/abc199/tasks/abc199_b

解説

https://atcoder.jp/contests/abc199/submissions/22039415

この問題は色々な解法が考えられるが、計算量が最も良いものを選択した。
求めたい整数xはとある範囲に限定される。
その範囲は、N個の[Ai,Bi]の積集合、つまり、すべてが重なる部分の範囲にある数となる。
なので、範囲の積集合を計算しよう。

範囲の積集合

問題のサブ課題としてこういった要望は良く出てくる。
[A,B]と[C,D]が重なっている範囲は[max(A,C),min(B,D)]となる。
この操作を繰り返していけばすべてが重なっている範囲を求めることができる。
最初は全部の範囲を網羅する必要があるので、初期状態は[-∞,∞]としておく。

注意点として、重なる領域が存在しない場合は、出力された領域[A,B]がA＞Bとなる。
この場合は重なる領域が存在しないことになるので、注意。
よって、答えはすべての重ねた領域[lft,rht]についてrht-lft+1となるが、
lft＞rhtのばあいは負数になるため、その場合は答え無しとするために0とmaxを取って答えとする。

※ lftはleft, rhtはrightとして使用している

int N, A[101], B[101];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
    rep(i, 0, N) cin >> B[i];

    int lft = -inf, rht = inf;
    rep(i, 0, N) {
        chmax(lft, A[i]);
        chmin(rht, B[i]);
    }

    int ans = max(0, rht - lft + 1);
    cout << ans << endl;
}