The question is:
Dilworth is the world's most prominent collector of Russian nested dolls: he literally has thousands of them! You know, the wooden hollow dolls of different sizes of which the smallest doll is contained in the second smallest, and this doll is in turn contained in the next one and so forth. One day he wonders if there is another way of nesting them so he will end up with fewer nested dolls? After all, that would make his collection even more magnificent! He unpacks each nested doll and measures the width and height of each contained doll. A doll with width w1 and height h1 will fit in another doll of width w2 and height h= if and only if w1 < w2 and h1 < h2. Can you help him calculate the smallest number of nested dolls possible to assemble from his massive list of measurements?
I know this problem can be solved by maximum bipartite matching tecnique but I want to know is there any way to solve using LIS?
If we have
w1 <= w2 and
h1 <= h2 instead of
w1 < w2 and
h1 < h2 I have an O(n2logn) solution using LIS as follow:
Initially we sort dolls by their
w values (and
h In the next priority) and then try to remove LIS from new order of dolls. number of times we can remove LIS from our dolls is the answer.
But it's obvious that my solution shouldn't work for original version of MDOLLS with
w1 < w2 and
h1 < h2 conditions.
Please help me to know is there a solution using LIS for MDOLLS?