Choosing boxes

You are given a collection of boxes, each with its own size. You are then given products one at a time, and you have to choose a large enough box for each product. Each box can be used only once.

Example: The box sizes are $[4,4,6,8]$ and you are given products as follows:

• The size of the product $1$ is $5$. You choose the box of size $6$.
• The size of the product $2$ is $5$. You choose the box of size $8$.
• The size of the product $3$ is $4$. You choose a box of size $4$.
• The size of the product $4$ is $6$. There is no box large enough.
• The size of the product $5$ is $1$. You choose the box of size $4$.

In a file nextbox.py, implement the function find_boxes that takes a list of box sizes and a list of products sizes in order of processing as parameters. The function should return a list of the box sizes chosen for each products. The box size should be $-1$ if no box was found for the product.

The function should be efficient even if both lists are long. The last function call in the code template tests this situation.

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