Sinulla on laatikoita, joista jokaisella on tietty koko. Sinulle annetaan yksi kerrallaan tuotteita, ja sinun tulee valita kullekin tuotteelle pienin riittävän suuri laatikko. Samaa laatikkoa voi käyttää vain kerran.
Esimerkki: Laatikoiden koot ovat [4,4,6,8] ja sinulle tulee tuotteita seuraavasti:
- Tuotteen 1 koko on 5. Valitset sille laatikon kokoa 6.
- Tuotteen 2 koko on 5. Valitset sille laatikon kokoa 8.
- Tuotteen 3 koko on 4. Valitset sille laatikon kokoa 4.
- Tuotteen 4 koko on 6. Tuotteelle ei löydy laatikkoa.
- Tuotteen 5 koko on 1. Valitset sille laatikon kokoa 4.
Toteuta tiedostoon nextbox.py funktio find_boxes, jolle annetaan listoina laatikoiden koot sekä tuotteiden koot käsittelyjärjestyksessä. Funktion tulee palauttaa lista, joka ilmoittaa kullekin tuotteelle laatikon koon tai luvun -1, jos sopivaa laatikkoa ei löytynyt.
Funktion tulee toimia tehokkaasti silloinkin, kun molemmat listat ovat suuria. Tehtäväpohjan viimeinen funktiokutsu testaa tällaista tilannetta.
def find_boxes(boxes, products):
# TODO
if __name__ == "__main__":
print(find_boxes([4, 4, 6, 8], [5, 5, 4, 6, 1]))
# [6, 8, 4, -1, 4]
print(find_boxes([1, 2, 3, 4], [1, 1, 1, 1, 1]))
# [1, 2, 3, 4, -1]
print(find_boxes([2, 2, 2, 2], [1, 1, 1, 1, 1, 1]))
# [2, 2, 2, 2, -1, -1]
print(find_boxes([1, 1, 1, 1], [2, 2]))
# [-1, -1]
boxes = []
products = []
for i in range(10**5):
boxes.append(i % 100 + 1)
products.append(3 * i % 97 + 1)
result = find_boxes(boxes, products)
print(result[42]) # 30
print(result[1337]) # 35
print(result[-1]) # 100