Varaukset

Annettuna on lista, jossa on varauksia päiväväleinä. Jokainen väli on pari $(a,b)$, missä $1 \le a \le b$: varaus alkaa päivänä $a$ ja päättyy päivänä $b$.

Tehtäväsi on tutkia, onko listassa kahta varausta, jotka menevät päällekkäin eli niissä on yksi tai useampi yhteinen päivä.

Esimerkiksi lista $[(4,7),(1,2)]$ tarkoittaa, että ensimmäinen varaus on päivästä $4$ päivään $7$ ja toinen varaus on päivästä $1$ päivään $2$. Nämä varaukset eivät mene päällekkäin. Listassa $[(4,7),(1,5)]$ varaukset sen sijaan menevät päällekkäin, koska molemmat varaukset sisältävät päivät $4$ ja $5$.

Toteuta tiedostoon reservations.py funktio check_overlapping, jolle annetaan varaukset listana. Funktion tulee palauttaa True, jos jotkin kaksi varausta menevät päällekkäin, ja False muuten.

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

import random

def check_overlapping(reservations):
    # TODO

if __name__ == "__main__":
    print(check_overlapping([])) # False
    print(check_overlapping([(1, 3)])) # False
    print(check_overlapping([(4, 7), (1, 2)])) # False
    print(check_overlapping([(4, 7), (1, 5)])) # True
    print(check_overlapping([(1, 1), (2, 2)])) # False
    print(check_overlapping([(1, 1), (1, 1)])) # True
    print(check_overlapping([(2, 3), (5, 5), (3, 4)])) # True
    print(check_overlapping([(2, 3), (5, 5), (1, 4)])) # True
    print(check_overlapping([(2, 3), (5, 5), (1, 5)])) # True

    reservations = [(day, day) for day in range(1, 10**5+1)]
    random.shuffle(reservations)
    print(check_overlapping(reservations)) # False

    reservations.append((42, 1337))
    random.shuffle(reservations)
    print(check_overlapping(reservations)) # True