jaydo
Newbie level 1
- Joined
- Dec 25, 2013
- Messages
- 1
- Helped
- 0
- Reputation
- 0
- Reaction score
- 0
- Trophy points
- 1
- Activity points
- 16
Hi
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
) - 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?
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.
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
) - 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?
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.