CSES - Paritus

Annettuna on nn lukuväliä muotoa [x,y][x,y] (missä xyx \le y) sekä mm kokonaislukua. Tehtäväsi on muodostaa mahdollisimman monta paria, joissa on lukuväli ja jokin sen sisällä oleva luku. Jokainen luku ja lukuväli saa olla mukana korkeintaan yhdessä parissa. Kuinka monta paria voidaan korkeintaan muodostaa?

Voit olettaa, että nn ja mm ovat korkeintaan 10510^5 ja että kaikki luvut ovat korkeintaan 10910^9.

Toteuta tiedostoon matching.py funktio count, joka kertoo montako paria voidaan korkeintaan muodostaa. Lista a sisältää lukuvälit ja lista b sisältää luvut.

def count(a, b):
    # TODO

if __name__ == "__main__":
    print(count([(4,6)], [1, 7])) # 0
    print(count([(2,9), (1,8)], [5])) # 1
    print(count([(1,5), (6,8)], [5, 2])) # 1
    print(count([(6,6), (3,8), (2,5)], [4, 6, 5])) # 3
    print(count([(4,7), (2,6), (8,9), (1,10)], [11, 3, 8, 2, 6])) # 4
    print(count([(4,7), (2,6), (8,9), (5,7)], [11, 3, 8, 2, 6])) # 3

Selitys: Neljännessä esimerkissä yksi mahdollinen tapa muodostaa kolme paria on liittää luku 44 väliin [2,5][2,5], luku 55 väliin [3,8][3,8] ja luku 66 väliin [6,6][6,6].