SPOJ : MDOLLS - Nested Dolls

Source of Question 

First of all the question is bit confusing , so basically question wants to say that , you have to find minimum remaining dolls which are not nested i.e after nesting all the possible dolls , how many dolls are left which are not nested.

EXAMPLE : 

let we have 3 dolls whose widths and heights are [ 10 , 20 ] , [ 20 , 20 ] and [30 , 21].

In this 1st doll can be put into the 3dr doll , now the space left inside the 3rd doll is the space of 1st doll , so 2nd  doll can not be put inside the 3rd doll now. So the remaining dolls which are not nested is doll 1 and doll 2 i.e two dolls.

So the minimum dolls which are left after nesting is 2.

Solution Approach

If we put a smaller doll whose dimensions are closest to the larger , doll's dimensions in which we are putting it , then the remaining space inside the larger doll will be maximum possible( i.e the space of the smaller doll ) , which will increase the number of dolls to be nested , So that the remaining dolls which are not able nested will be minimum.

- How tho Find the dolls which are closest to its Dimensions ?

If we sort the dolls in decreasing order of there width , then all the adjacent dolls dimensions are nearly closer.

- Why sort in Decreasing order of there width ?

Because first we have to pick the largest doll , so that we can put smaller doll into it.

- What if the two dolls have same width ?

Now , we have to options , either sort in decreasing order of there heights or in increasing order of there heights.

Now take an example to see how to sort the dimensions if the two or more dolls have same width :

consider 10 dolls whose dimensions are below :

Doll 1 :

(83 ,  58) , since there is no dolls so the remaining dolls after nesting = 1

and remaining space = (83 , 58)

Doll 2 :

(80 , 15) it can be put inside the doll 1 , so

(83 , 58) --> (80 , 15) , now space inside he doll 1 is (80 , 15).

Can we replace the whole doll with only 2nd doll ? 🤔

Yes , because now we can only put dolls inside the 1st dolls whose dimensions are less than the 2nd doll's dimensions.

remaining dolls after nesting = 1

and remaining space = (80 , 15)

Doll 3 :

(76 , 55) it can not be put inside the (80 , 15) since ( 55 > 15 )

remaining dolls after nesting = 2

and remaining spaces = (80 , 15) ,  (76 , 55)

Now , Observe that the dolls place above 🙄 are in decreasing order of there widths and in increasing order of there height. So now whenever a new doll comes it is obvious that its width is not greater than any of the remaining dolls. So by height of new doll , we can put new doll inside any of the remaining doll's spaces , But we have to make dolls nested as many as possible so that the remaining dolls will be minimum.

Therefore we have to choose the dolls whose height is minimum in the available spaces but greater than the new doll.

Since the available spaces ( i.e remaining dolls ) already sort in increasing order of there height , so we can easily find the doll whose height is minimum but greater than the new doll in O(n) by iterating from left to right or in O(logn) by using binary search.

But if no doll ( space ) available whose height is greater than the new doll then we put the new doll in the left of the available dolls . so that the available dolls ( space ) are remain sorted in increasing order of height.

That is why we have to sort the dolls in decreasing order of there heights if there widths are same.😲 

Doll 4:

(76,88) , it is also can not be put into in any available space.

remaining dolls after nesting = 3

and remaining spaces = (80 , 15) ,  (76 , 55) , (76 , 88)

Doll 5:

(71,65) , it can be put into the 3rd doll ( i.e (76,88) ) and replace (76,88) by (71,65)

remaining dolls after nesting = 3

and remaining spaces = (80 , 15) ,  (76 , 55) , (71 , 65)

Doll 6:

(65,66) , it is also can not be put in any of the available spaces.

remaining dolls after nesting = 4

and remaining spaces = (80 , 15) ,  (76 , 55) , (71 , 65) , (65 , 66)

Doll 7:

(62,47) , it can be put in any of the 2nd , 3rd , 4th available space but we have to increase the nesting so we have to choose the doll( space ) with minimum height i.e. 2nd doll (76, 55) and replace it with (62,47)

remaining dolls after nesting = 4

and remaining spaces = (80 , 15) ,  (62 , 47) , (71 , 65) , (65 , 66)

Doll 8:

(57,19) , it will put in the 2nd doll (62 , 47) and replace (62 , 47) by (57 , 19)

remaining dolls after nesting = 4

and remaining spaces = (80 , 15) ,  (57 , 19) , (71 , 65) , (65 , 66)

Doll 9:

(46,64) , it will be put into the 3rd doll (71 , 65) and replace (71 , 65) by (46,64)

remaining dolls after nesting = 4

and remaining spaces = (80 , 15) ,  (57 , 19) , (46 , 64) , (65 , 66)

Doll 10:

(8,25) , it will be put into the 3rd doll (46 , 64) and replace (46 , 64) by (8 , 25)

remaining dolls after nesting = 4

and remaining spaces = (80 , 15) ,  (57 , 19) , (8 , 25) , (65 , 66)

--------------------------------------------------------------------------------------------------------------------------

So after all the minimum number of dolls which are remain after nesting ( i.e dolls which are not possible to be nested ) = 4

These are the dolls which are nested:

(83 , 58)  --> (80 , 15)  🤡

(76 , 55)  -->  (62 , 47)  -->  (56 , 19)  🤡

(76 , 88)  -->  (71 , 65)  -->  (49 , 64)  -->  (8 , 25)  🤡

(65 , 66)  🤡


Summary

So basically we first have to sort the array containing doll's dimensions in decreasing order of there width , if some dolls have same width then sort in increasing order of height.

Then take another array D where we put the dolls which are not nested.

Then iterate from the left of the array , for first doll there is no doll to nested there we put the first doll in array D , then go to the next doll ( since we already sorted the dolls acc. to width therefore the next dolls widths is always less or equal to the dolls which are present in the array D ) so we have to find the first doll whose width is greater than its width and height is less than its height ( so that nesting can be done ) , and then replace the doll in D by the new doll ( because after putting the new doll inside the doll present in array D will be equal to the space of the new doll , so now only dolls whose dimensions are smaller then the new doll can be put inside it , therefore we can replace the doll present in D by new doll ).  But if such type of doll is not present in the array D then no nesting possible so we put the new doll at the end of the array D.

And repeatedly do this , after iterate to all the dolls ,  the remaining doll which are not nested = size of the array D ( which is the minimum number of doll which are not nested ) 

SIMILAR PROBLEM

CODE