Laatikon valinta

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