Intervals dins d'intervals P40985


Statement
 

pdf   zip

thehtml

Donats diversos intervals [ai, bi], determineu quants d’ells estan continguts en algun altre.

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb un nombre n entre 0 i 104, seguit de n intervals de nombres enters [ai, bi]. Suposeu ai < bi, i que per a tot parell i ≠ j, ai ≠ aj, bi ≠ bj, i ai ≠ bj.

Sortida

Per a cada cas, escriviu el nombre d’intervals continguts en algun altre.

Pista

La solució esperada té cost Θ(n logn). Usar el procediment sort() per ordenar amb algun criteri adequat us hauria de ser útil.

Public test cases

  • Input

    3   0 1  2 3  4 5
3   0 5  1 4  2 3
0
1   -3 0
4   -30 30  20 40  -10 10  -40 -20

    Output

    0
2
0
0
1
    • Information
    Author
    Amalia Duch
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++