Given n boxes with length and width. A box with smaller length and smaller width can be put on a box with larger length and larger width.
Each box height is 1. Find the tallest box that they can put together. In general, we can build the box with m-dimension.
For example, if we have:
boxes = {
{0, 0},
{1, 2},
{1, 1},
{3, 4},
{4, 3},
{4, 4},
{3, 3} };
A longest possible combination is: (4, 4)->(3, 4)->(3, 3)->(1, 2)->(1, 1)->(0, 0). So tallest height is 6.
For n boxes, we do comparison between each box. If box[j] can be put on box[i], then we put an edge from box[i]->box[j].
In this way, we build a graph among boxes. Gathering all the boxes which doesn’t has parent, we use BFS to iterate.
The max number of iteration will be the result.
Assume a graph is like below, we can see the total iteration starting from v1, v2 to the end is 4.
Check my code on github: link