0
$\begingroup$

There are n Boxes. Each box has a size. A box can be put into another box only if the size of box who hold the other box is at least twice as large as the size of box which is held.

Each box can hold at most one box, and the box which is held by another box become invisible.

Please, help to find minimal number of boxes which are visible.

EXAMPLE : IF THEIR ARE 8 BOXES WHOSE SIZE ARE : {2 5 7 6 9 8 4 2}

THEN MINIMUM NUMBER OF BOXES THAT ARE VISIBLE ARE 5.

$\endgroup$
1
$\begingroup$

Here's an algorithm that takes $O(n)$ if the box sizes are in sorted order $0<b_1\le b_2\le \ldots \le b_n$:

  1. Let $i\leftarrow1$, $j\leftarrow 1$
  2. If $2b_i\le b_j$, let $i\leftarrow i+1$ [that is, the smallest not yet hidden box is placed into the smallest box available for hiding a box]
  3. If $j<n$ let $j\leftarrow j+1$ and go to step 2 [that is, box $j$ has either been used for hiding a smaller box or could not be used for hiding a smaller box]
  4. Output $n+1-i$ and terminate.

Here's a C program code for sorted box sizes b[0] ... b[n-1]:

int i=0; for (int j=0; j<n; j++) if (2*b[i]<=b[j]) i++; return n-i;
$\endgroup$
3
  • $\begingroup$ Box which is held by another box cannot hold any other box have you keep this thing in consideration?. $\endgroup$ Dec 13 '13 at 14:54
  • $\begingroup$ @user3001932 I do not read that condition from the problem statement. After all, the box in the box becomes "invisible". In fact, cf. the example which is supposed to have the solution $2\in 4\in 8, 2\in 5, 6, 7, 9$ with $8,5,6,7,9$ visible $\endgroup$ Dec 13 '13 at 15:07
  • $\begingroup$ I mean to say if 2 is inside 4 then 2 cannot have any other box inside it.and in this example it can be done that one 2 is inside 5,one 2 is inside 6,4 is inside 8,so visible are 5,6,7,8,9 $\endgroup$ Dec 13 '13 at 15:15
0
$\begingroup$

Simple algorithm:
$L := \text{list of unplaced boxes}$
$H := \text{list of hidden boxes}$
$S := \text{list of shown boxes}$

  1. Take the biggest box from $L$ and move it to $S$, call it $b$
  2. If there is a Box in $L$ with size $< \frac {|b|}2$, put it into $H$ and set $b$ to this box. Repeat until no more boxes can be hidden in the current $b$ (i.e. $L$ is empty or contains only boxes with size $\ge \frac{|b|}2$)
  3. If $L$ is nonempty, go to 1.
  4. Return $|S|$
$\endgroup$
2
  • $\begingroup$ What willl be complexity for this algorithm.?Wont it be o(n^2).The n range is of 10^5.So is their any better way $\endgroup$ Dec 13 '13 at 14:37
  • $\begingroup$ @user3001932 Hagen von Eitzen pointed out a more efficient way; this one will be $\mathcal O(n)$ plus the cost of finding the smaller box, i.e. maybe $\mathcal O(n\log n)$ if $L$ is sorted and we use a good searching algorithm. $\endgroup$
    – AlexR
    Dec 13 '13 at 14:43
0
$\begingroup$

Finding the minimum number of boxes that are visible is equivalent to finding the maximum number of disjoint pair of boxes that one contains another. Hence, we can build a graph representing the inclusion relation. Number of boxes minus the maximum number of matching in this graph is the answer. Maybe greedy approach also works for this problem, I would like to see a proof for that.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.