You are given a lot of cuboid boxes with different length, breadth and height. You need to find the maximum subset which can fit into each other.
For example:
If Box A has LBH as 7 8 9
If Box B has LBH as 5 6 8
If Box C has LBH as 5 8 7
If Box D has LBH as 4 4 4
then answer is A,B,D
A box can fit into another only and only if all dimensions of that is
less than the bigger box. Also Rotation of boxes is not possible.
Answer:
I think this is a modification of longest increasing subsequence problem . First , sort by length then find the longest increasing subsequence by width. Now, in this solution find longest increasing subsequence by height . This would be the answer to this question.
For example:
If Box A has LBH as 7 8 9
If Box B has LBH as 5 6 8
If Box C has LBH as 5 8 7
If Box D has LBH as 4 4 4
then answer is A,B,D
A box can fit into another only and only if all dimensions of that is
less than the bigger box. Also Rotation of boxes is not possible.
Answer:
I think this is a modification of longest increasing subsequence problem . First , sort by length then find the longest increasing subsequence by width. Now, in this solution find longest increasing subsequence by height . This would be the answer to this question.
No comments:
Post a Comment