Annettuna on n lukuväliä muotoa [x,y] (missä x \le y) sekä m 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ä n ja m ovat korkeintaan 10^5 ja että kaikki luvut ovat korkeintaan 10^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 4 väliin [2,5], luku 5 väliin [3,8] ja luku 6 väliin [6,6].