Voit olettaa, että listalla on enintään $10^5$ lukua ja että jokainen luku on väliltä $1 \dots 10^9$. Tavoitteena on, että algoritmin aikavaativuus on $O(n)$ tai $O(n \log n)$.
Toteuta tiedostoon
interval.py
funktio count
, joka ilmoittaa, montako lukua listalta voidaan enintään poimia halutulla tavalla.def count(t): # TODO if __name__ == "__main__": print(count([1, 1, 1, 1])) # 1 print(count([10, 4, 8])) # 1 print(count([7, 6, 1, 8])) # 3 print(count([1, 2, 1, 2, 1, 2])) # 2 print(count([987654, 12345678, 987653, 999999, 987655])) # 3Selitys: Listalta $[10, 4, 8]$ voidaan poimia vain yksi luku, sillä minkään kahden luvun erotus ei ole tasan $1$. Listalta $[7, 6, 1, 8]$ on mahdollista poimia $3$ lukua järjestyksessä $6$, $7$ ja $8$.