Question

link

Objects of different volumes must be packed into a finite number of bins or containers each of volume V in a way that minimizes the number of bins used.

Solution

Explanation from here:

  1. Build a binary tree. Each branch in the tree contains a sprite.
  2. Each leaf node represents available space.
  3. Initially the tree has just the root node, which represents all available space.
  4. To add a sprite to the tree, search the tree for an unoccupied (leaf) node big enough to hold the sprite.
  5. Turn that node from a leaf into a branch by setting the sprite as the node’s occupant and giving the node two children.
  6. One child represents the remaining space to the right of the sprite;
  7. the other represents the remaining space below the sprite and the first child.

For detailed implementation and code, refer to this comprehensite guide. BTW, it’s used for auto generating CSS Sprites which puts images into a large graph.