Annettuna on lista lukuja ja tehtäväsi on selvittää, montako lukua listalta voidaan valita siten, että minkään kahden valitun luvun erotus ei ole suurempi kuin x.
Voit olettaa, että listalla on enintään 10^5 lukua ja x ja jokainen listan luku on väliltä 0 \dots 10^9. Tavoitteena on, että algoritmin aikavaativuus on O(n) tai O(n \log n).
Toteuta tiedostoon bigset.py funktio find, joka ilmoittaa montako lukua listalta voidaan enintään valita.
def find(t, x):
# TODO
if __name__ == "__main__":
print(find([10, 10, 10, 10], 0)) # 4
print(find([4, 2, 7, 1], 0)) # 1
print(find([7, 3, 1, 5, 2], 2)) # 3
print(find([7, 3, 1, 5, 2], 1000)) # 5
print(find([19, 4, 7, 17, 3, 15, 10], 5)) # 3
print(find([10000, 987654, 123456, 139562, 13613225], 50000)) # 2
Selitys: Toisessa esimerkissä listalla [4, 2, 7, 1] kaikki luvut ovat erisuuria, joten voimme valita vain yhden luvun, sillä muuten löytyisi aina lukupari, jonka erotus on suurempi kuin 0. Kolmannessa esimerkissä listalta [7, 3, 1, 5, 2] voidaan valita kolme lukua: 3, 1 ja 2 ja näiden lukujen väliset erot ovat kaikki korkeintaan 2.