#### electroRF

##### Member

I have an algorithmic question.

You have boxes of sizes

**5 x 9 x 8**.

You have

**n**items to ship.

You're required to use "first-hit" algorithm - i.e. every item you get (out of the n items) , you insert it to the first box that can contain it.

The obvious way would take

**O(n²)**(linear-scan the boxes for every item you get).

However - You are required to do it in

**O(nlog(n))**-

**HOW?**

I saw a solution which says:

"We will maintain a sorted list of boxes,

**first by box capacity**, then by box number.

when we receive a new item, we look for the first record with capacity greater than or equal to

the iterm's weight."

**My question is:**

How do you sort boxes by capacity?

How do you sort boxes by capacity?

You can have an item 2x2x2, which doesn't fit into larger-capactiy box of 1x9x8, but does fist into smaller-capacity box of 2x2x2.

Thank you very much.