我正在寻找指向以下问题的解决方案的指针：我有一组矩形，这些矩形的高度已知，并且x位置也是如此，我想将它们打包为更紧凑的形式。我想要一个小的绘图(所有矩形的宽度都相同，但实际生活中宽度可能会有所不同)，而不是。

-r1-
  -r2--
     -r3--
       -r4-
        -r5--

就像是。

-r1-  -r3-- 
  -r2-- -r4-
         -r5--

所有提示将不胜感激。我不一定要寻找"最佳"解决方案。

解决方案

像这样吗？

• 按x位置对矩形集合进行排序
• 编写一种方法来检查在x轴的特定间隔上存在哪些矩形

Collection<Rectangle> overlaps (int startx, int endx, Collection<Rectangle> rects){
...
}

• 遍历矩形的集合

Collection<Rectangle> toDraw;
Collection<Rectangle> drawn;
foreach (Rectangle r in toDraw){
Collection<Rectangle> overlapping = overlaps (r.x, r.x+r.width, drawn);
int y = 0;
foreach(Rectangle overlapRect in overlapping){
y += overlapRect.height;
}
drawRectangle(y, Rectangle);
drawn.add(r);
}

问题是一个简单的变体，但是我们可能会获得一些有关为"装箱"问题开发的启发式方法的提示。关于此的文章很多，但是此页是一个良好的开端。

将类似俄罗斯方块的游戏放入网站。根据参数生成掉落的块和游戏区域的大小。根据设计的紧凑性(更少的自由空间=更多的积分)向玩家奖励积分。让网站访问者为我们执行工作。

矩形是否都具有相同的高度？如果它们是问题，而问题仅在于将每个矩形放入哪一行，那么问题归结为对所有形式为"矩形X不能与以下行在同一行"的矩形对(X，Y)的一系列约束。矩形Y"是指矩形X在x方向上与矩形Y重叠。

为此，采用"贪婪"算法对矩形进行从左到右的排序，然后将每个矩形依次分配给其适合的编号最小的行。因为矩形是从左到右处理的，所以只需要担心当前矩形的左边缘是否会与其他任何矩形重叠，这在某种程度上简化了重叠检测算法。

我无法证明这是最佳解决方案，但另一方面也无法想到任何反例。任何人？

Topcoder进行了竞争，以解决此问题的3D版本。获胜者在这里讨论了他的方法，这可能对我们来说很有趣。

我以前曾处理过这样的问题。最直观的图片可能是大矩形在底部，小矩形在顶部，有点像将它们全部放入一个容器中并摇晃它，使较重的矩形掉到底部。因此，要做到这一点，首先要按面积(或者宽度)递减的顺序对数组进行排序-我们将首先处理较大的项目并建立起地面的图片。

现在的问题是，如果我正确理解的话，就是将y坐标分配给一组给出x坐标的矩形。

遍历矩形数组。对于每个矩形，将矩形的y坐标初始化为0。然后通过增加该矩形的y坐标进行循环，直到它不与任何先前放置的矩形相交为止(我们需要跟踪先前放置过的矩形)。承诺刚找到的y坐标，然后继续处理下一个矩形。