Maximum subset of Cuboid boxes that can fit into one another

Problem

 Given a lot of cuboid boxes with different length, breadth and height. We need to find the maximum subset which can fit into each other.

Example

For example:
If Box 1 has LBH as 7 8 9
If Box 2 has LBH as 5 6 8
If Box 3 has LBH as 5 8 7
If Box 4 has LBH as 4 4 4 then answer is 1,2,4

A box can fit into another only and only if all dimensions of that is less than the bigger box.Rotation of boxes is not possible.

Solution

Method 1 - Using DP
The problem can be solved using dynamic programming.
sort all the boxes as per length and then its simply find the Length of Longest increasing subsequence.
Here is the basic algo:

A box can fit into another if and only if all its dimensions are lesser than that of the bigger box. So, we need to sort the boxes first on some parameter, say length.

With this sorting, the boxes can be put into each other at least from the length perspective.

To fix the width perspective, find the maximum increasing subsequence by width from this list. The resulting subsequence would be sorted both on length and breadth.

Now, find maximum increasing subsequence based on height and we got the answer!


Note: We first sorted on length, then chose MIS for breadth and then height. It still needs to be analyzed if the order of choosing these parameters will yield a different result.

For instance, if array is sorted on breadth first, then MIS based on length is extracted and then MIS of height is extracted, would it be different from our original case?

Probably, if there is only one maximum subsequence of boxes, then all orders will yield the same result. If they do not, then we have to run all permutations of choosing l,b,h and choose the maximum among them.