はまやんはまやんはまやん

hamayanhamayan's blog

Nested Segments [CSAcademy #56 A]

https://csacademy.com/contest/round-56/task/nested-segments/

[L[i],R[i]]の区間がN個ある。
この内、最低1つでも他の区間にネストされている区間は何個あるか。

区間iが区間jにネストされているのは、L[j]

解法

全ての区間について、他の区間でネストしているものが無いか愚直に探す。
あれば、答えとしてカウントする。

int N, L[1010], R[1010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> L[i] >> R[i];

    int ans = 0;
    rep(i, 0, N) {
        int ok = 0;
        rep(j, 0, N) if (j != i) if (L[j] < L[i] and R[i] < R[j]) ok = 1;
        if (ok) ans++;
    }
    cout << ans << endl;
}