Lukuvälit

Annettuna on lista, jossa on lukuvälejä. Tehtäväsi on selvittää, moniko lukuväli on toisen lukuvälin sisällä.

Lukuväli $(a,b)$ muodostuu kokonaisluvuista $a,a+1,\dots,b$. Esimerkiksi lukuväli $(3,7)$ muodostuu luvuista $3,4,5,6,7$. Lukuväli $(a_1,b_1)$ on lukuvälin $(a_2,b_2)$ sisällä, jos $a_2 \le a_1$ ja $b_1 \le b_2$. Esimerkiksi lukuvälit $(4,6)$, $(3,4)$ ja $(5,7)$ ovat lukuvälin $(3,7)$ sisällä.

Esimerkiksi listassa $[(3,7),(1,2),(2,8),(1,4)]$ haluttu vastaus on $2$, koska lukuvälit $(3,7)$ ja $(1,2)$ ovat toisen lukuvälin sisällä. Lukuväli $(3,7)$ on lukuvälin $(2,8)$ sisällä, ja lukuväli $(1,2)$ on lukuvälin $(1,4)$ sisällä.

Toteuta tiedostoon intervals.py funktio count_nested, jolle annetaan lukuvälit listana. Funktion tulee palauttaa niiden lukuvälien määrä, jotka ovat toisen lukuvälin sisällä. Voit olettaa, että listassa ei ole kahta samaa lukuväliä.

Sinun tulee toteuttaa funktio niin, että se käsittelee tehokkaasti myös suuren määrän lukuvälejä. Funktion tulee antaa vastaus välittömästi myös tehtäväpohjan kahdessa viimeisessä testissä.

import random

def count_nested(intervals):
    # TODO

if __name__ == "__main__":
    print(count_nested([])) # 0
    print(count_nested([(1, 2)])) # 0
    print(count_nested([(1, 2), (3, 4)])) # 0
    print(count_nested([(1, 3), (2, 4)])) # 0
    print(count_nested([(1, 4), (2, 3)])) # 1
    print(count_nested([(1, 4), (1, 3)])) # 1
    print(count_nested([(1, 4), (2, 4)])) # 1
    print(count_nested([(1, 1), (1, 2), (1, 3)])) # 2
    print(count_nested([(1, 6), (2, 5), (3, 4)])) # 2
    print(count_nested([(1, 4), (2, 5), (3, 6)])) # 0

    intervals = [(x+1, x+3) for x in range(10**5)]
    random.shuffle(intervals)
    print(count_nested(intervals)) # 0

    intervals = [(x+1, 2*10**5-x) for x in range(10**5)]
    random.shuffle(intervals)
    print(count_nested(intervals)) # 99999