問題概要

数直線において、

$L_{1}$ から $R_{1}$ までの部分をすべて赤色で塗り
$L_{2}$ から $R_{2}$ までの部分をすべて青色で塗った

このとき、赤色と青色の両方で塗られている部分の長さを求めよ。

解法 (1)：区間の交差

数学 IA の「連立不等式」に近い考え方をする。2 つの区間

$a \le x \le b$
$c \le x \le d$

について、これらの双方に含まれている区間を求めたいとしよう。この答えは本当にシンプルに、次のように書ける。

$l = \max(a, c)$
$r = \min(b, d)$

として、

$l \le r$ ならば、 $l \le x \le r$
そうでないならば、共通部分なし

つまり、左端は max をとり、右端は min をとればよいのだ。2 個の区間に限らず、 $N$ 個の区間となっても同様にできる。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int L1, R1, L2, R2;
    cin >> L1 >> R1 >> L2 >> R2;
    
    int l = max(L1, L2);
    int r = min(R1, R2);
    if (l <= r) cout << r - l << endl;
    else cout << 0 << endl;
}

解法 (2)：マスを用意して色塗りする

数直線上で実際にマスを用意して、実際に色を塗る方法もある。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int L1, R1, L2, R2;
    cin >> L1 >> R1 >> L2 >> R2;
    
    // 数直線にマスを用意して、実際に色を塗る
    vector<bool> isred(1000, false);  // 制約が R1, R2 <= 100 なので、1000 あれば十分
    vector<bool> isblue(1000, false);
    for (int i = L1; i < R1; ++i) isred[i] = true;
    for (int i = L2; i < R2; ++i) isblue[i] = true;
    
    // 両方の色がついたマスを数える
    int res = 0;
    for (int i = 0; i < 1000; ++i) {
        if (isred[i] && isblue[i]) ++res;
    }
    cout << res << endl;
}