algorithm - 尝试最小化包含不同整数形状的矩形的矩形空间时可以避免回溯吗？

Question

我的问题的抽象是在笛卡尔平面中有很多矩形。这些矩形具有已知的整数大小，并且必须具有整数坐标，它们的横坐标(水平坐标)是已知且固定的，只有它们的纵坐标(垂直坐标)可能会有所不同。

问题是找到包含所有给定矩形的最小矩形最小的那些坐标。这意味着它应该有最小高度，因为它的宽度是固定的，因为小矩形有固定的横坐标。

我不知道我是否应该使用回溯或有更快的方法，我可以想象在 50 个矩形中计算正确的解决方案需要一些可测量的时间，而贪心算法并不适合我。

编辑:对不起，我现在意识到我不够清楚。当我第一次问这个问题时，我正在构建一个日历应用程序。经理会为他的团队填写事件:

• 事件 A 从下午 2 点开始。下午 4 点结束。
• 事件 B 从下午 5 点开始。下午 6 点结束。
• 事件 C 从下午 4 点开始。下午 6 点结束。
• 事件 D 从下午 2 点开始。下午 3 点结束。
• 事件 E 从下午 3 点开始。下午 5 点结束。

我想在时间轴上显示这些事件，我希望它们占用尽可能少的屏幕空间，不要重叠(因为经理希望在其矩形中查看每个事件，并在该矩形中查看描述)。

上述示例的最佳安排如下:

+-----+-----+
|  A  |  C  |
+---+-+-+---+
| D | E | B |
+---+---+---+

A和C在一条线上，D、E、B在另一条线上。贪婪的方法会将 A 和 B 放在同一行，C 和 D 放在另一行，E 放在第三行。

Answer 1

如果我没看错你的问题，你需要找到一个覆盖给定矩形集的最小矩形——对吗？

而且它的横坐标范围是输入条件固定的，那么只需要求纵坐标范围就可以了？

如果是这样，只需扫描给定的一组矩形以获得它们的“最小底部”和“最大顶部”，它们将定义所寻找的矩形。