Editorialist: Raj Shah
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Basic Mathematics, Greedy Algorithm
PROBLEM STATEMENT:
PROBLEM:
-
You are given a number of empty rectangular cartons of different sizes which are open at the top, so smaller cartons can be stacked inside bigger cartons provided each of its sides is less than or equal to the corresponding side of the other.
-
For example, a 10 × 8 carton can be stacked inside a 9×12 carton or a 10×10 carton, but not inside a 9×9 carton.
-
Your goal is to decide how to stack them one inside the other so that they occupy the minimum floor area.
-
Example: You have five cartons labeled A, B, C, D, and E as follows:
- A: 10 × 13
- B: 11 × 9
- C: 12 × 8
- D: 7 × 6
- E: 13 × 7
-
One possible stacking is D inside B inside A, with C and E separate. This occupies floor area A + C + E = 130 + 96 + 91 = 317.
-
Another possible stacking is D inside C inside A, with B and E separate. This occupies floor area A+B +E = 130+99+91 =320.
-
Thus, the first arrangement is better.
QUICK EXPLANATION:
- Sort the boxes in descending order based on the maximum dimension value they have.
- Sub-sort the boxes having the same maximum dimension value in the descending order by their area.
- Now, iterate over the boxes and choose the first not visited box as your outermost box for a stack and mark it visited.
- Then go ahead and choose the box having maximum area and can go inside the previously chosen box and mark them both visited.
- Keep track of which box is chosen to put inside which box.
- In the end, when every box is visited, you have got your desired arrangement.
SOLUTIONS:
- Solution to Task-1:
- Table : Bold ones are visited, Italic ones were previously visited
Sorted First Iteration Second Iteration Third Iteration I: 15 × 8 I: 15 × 8 I: 15 × 8 I: 15 × 8 H: 9 × 14 H: 9 × 14 H: 9 × 14 H: 9 × 14 C: 8 × 13 C: 8 × 13 C: 8 × 13 C: 8 × 13 G: 12 × 10 G: 12 × 10 G: 12 × 10 G: 12 × 10 B: 9 × 12 B: 9 × 12 B: 9 × 12 B: 9 × 12 E: 7 × 12 E: 7 × 12 E: 7 × 12 E: 7 × 12 F: 11 × 11 F: 11 × 11 F: 11 × 11 F: 11 × 11 A : 10 × 11 A: 10 × 11 A: 10 × 11 A: 10 × 11 D: 11 × 9 D: 11 × 9 D: 11 × 9 D: 11 × 9
- So the first stack would be E in C in I.
- The second stack would be D in B in H.
- The third stack would be A in G.
- And the remaining final stack would be F alone.
- Answer = { [ E in C in I] , [ D in B in H] , [A in G] , [F]}