小编典典

找到包含所有矩形的最小区域

algorithm

这是一个面试问题。
给定了各种矩形的尺寸,我们必须找出可以包围所有矩形的矩形的面积(最小值)?矩形也可以旋转。

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

output:
88

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

我看过一个类似的问题,即在最小可能的区域中安装矩形 之前
,上述方法着眼于所有可能性,旋转,并确定所有布局情况下所有此类可能性中的最小值。
我们不能基于一种算法,首先找到矩形的面积之和,然后再寻找最大长度,最大宽度吗?


阅读 355

收藏
2020-07-28

共1个答案

小编典典

对于该问题,没有绝对的解决方案,但是有几种近似的解决方案,您可以在此处阅读其中的一些内容。

2020-07-28