2

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

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

我不知道我是否应该使用回溯或者有更快的方法，我可以想象在 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 放在第三条线上。

4

2 回答 2

1

我会保持事件的时间顺序。您正在构建日历，因此按时间顺序排列非常有意义。首先显示最先开始的事件。

我会以不同的方式解决屏幕空间问题，而不是通过重新包装元素。例如，减小元素大小，但当用户将鼠标悬停在元素上时，会显示带有更多信息的工具提示。当用户选择一个元素（用鼠标点击）然后显示完整的信息。

于 2014-03-10T14:12:42.443 回答
1

如果我正确阅读了您的问题，您需要找到一个最小矩形，它覆盖给定的一组矩形——对吗？

而且由于它的横坐标范围是由输入条件确定的，所以只需要找到纵坐标范围？

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

于 2014-03-09T01:29:30.503 回答