我不确定是否有算法可以解决这个问题。
将给定数量的矩形从左到右水平并排放置以形成一个形状。您将获得每个的宽度和高度。
您如何确定覆盖整个形状所需的最小矩形数量？
即，您将如何使用尽可能少的矩形重新绘制该形状？
我只能考虑尝试挤压尽可能多的大矩形，但这似乎效率低下。
有任何想法吗？
编辑：
给你一个数字 n ，然后是 n 个尺寸：
2
1 3
2 5
上面将有两个彼此相邻的尺寸为 1x3 和 2x5 的矩形。
我想知道在给定的矩形不能重叠的情况下，我最少需要多少个矩形来重新创建该形状。
由于您的矩形对齐得很好，因此问题变得更容易。您可以简单地从下到上创建矩形。每次执行此操作时，它都会创建新的形状进行检查。好处是，你所有的新形状都会also基本对齐，您可以根据需要重复。
首先，您要找到最小高度的矩形。制作一个具有相同高度的矩形，宽度作为形状的总宽度。从形状底部剪掉那么多。
您将留下多种形状。对于每个人，做同样的事情。
Finding the minimum height rectangle should be O(n). Since you do that for each group, worst case is all different heights. Totals out to O(n2).
例如：
在图像中，每个形状的最小值以绿色突出显示。生成的矩形是蓝色的，位于右侧。所需矩形的总数是图像中蓝色矩形的总数，7。
请注意，我解释这一点时就好像这些是物理矩形一样。在代码中，您可以完全取消宽度，因为它根本不重要，除非您想输出矩形而不是仅仅计算它需要多少个。
您还可以将“制作一个矩形并将其从形状中剪切”减少为简单地从构成该形状/子形状的每个矩形中减去高度。执行此操作后，具有 +ve 高度的形状的每个连续部分将组成一个新的子形状。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
