Search code examples
calgorithmmatharea

find smallest area that contains all the rectangles

This is an interview question.
We are given dimensions of various rectangles, we have to find out the area(minimum) of rectangle that can enclose all of them? rectangles can be rotated also .

test case:-
input:
3   //number of rectangles
8 8
4 3
3 4

output:
88

11x8:
+ - - - - - - + + - +
|             | |   |
|             | |   |
|             | + - +
|             | + - +
|             | |   |
|             | |   |
+ - - - - - - + + - +

i looked at a similar question asked before fitting rectangles in the smallest possible area
the above approach looks at all possibilities ,rotations, and determine the minimum over all such possibilities in all layout cases.
can't we base an algorithm in which we find the sum of area of rectangles first and then look for max length ,width?

Solution

  • There is no absolute solution to this problem, but there are several approximate solutions, you can read about some of them here.