7

假设给定一组闭合区间，其中每个区间的形式为 [l,r]。如果我们想从这个集合中选择两个区间，使得它们的交集大小乘以它们的并集大小是最大值。我们可以提供一个非平凡的算法来解决这个问题吗？

例如，如果我们有四个区间，[1,6]、[4,8]、[2,7]、[3,5]。最佳解决方案是选择[1,6]和[2,7]。答案是 (7-1) * (6-2) = 24。

实际上最初的问题需要我们选择（N>=2）个区间，但我认为我们可以证明最优解只包含两个区间：

如果最优解具有三个或更多区间：

[                     ]
            [               ]
                   [                          ]

我们可以看到，如果我们删除中间区间，权重不会减少。

4

2 回答 2

2

给定一组 N > 2 的重叠区间，这些区间可以最大化联合时间的交集，留出一个包含联合中最左边点的区间和一个包含联合中最右边点的区间。由于 N > 2，您至少还有一个其他区间。如果从集合中删除此区间，则不会减小区间并集的大小，因为您留出了区间以覆盖最左边和最右边的点。您只能通过删除间隔来增加交叉点的大小。因此，通过删除此间隔，您只能增加您试图最大化的产品，因此确实可以在 N = 2 处找到最佳解决方案。

对区间的端点集进行排序，并按升序遍历它。在平局的情况下，在最右边的点之前考虑最左边的点。跟踪一组区间，当你看到它的最左边点时将一个区间添加到集合中，当你看到它的最右边点时从集合中删除一个区间。

对于任何两个重叠的间隔，当其中一个已经存在并且您正要添加另一个时，将会有一个点。因此，如果在将区间添加到集合之前，将其与集合中已有的所有其他区间进行比较，则可以比较所有重叠区间对。因此，您可以计算要添加的区间与集合中所有其他区间之间的并集和交集的乘积，并跟踪看到的最大区间。

于 2012-06-02T05:31:35.810 回答
0

证明两个区间就足够了：选择适当包含在另一个区间中的区间是没有意义的。不失一般性，让区间为 [a1, b1], ..., [an, bn] 使得 a1 < ... < an。如果没有区间正确包含另一个区间，则 b1 < ... < bn。对于 i < j < k，它认为 ([ai, bi] intersect [aj, bj] intersect [ak, bk]) = ([ai, bi] intersect [ak, bk]) 和 union 相同，所以没有理由选择两个以上的区间。

O(n log n)-time algorithm：重新制定，问题是找到区间 [a, b] 和 [c, d] 最大化 (d - a) * (b - c)，因为这个乘积是负的，当且仅当区间不要相交。我们的算法是进行 O(n log n) 预处理，使我们能够在 O(log n) 时间内为每个间隔找到最佳配对。

让我们努力寻找 [a, b] 的最佳伴侣。做一些代数：(d - a) * (b - c) = d*b - d*c - a*b + a*c。由于 a, b 是固定的，我们可以去掉 -a*b 项并在所有区间 [c, d] 上最大化内积 <(a, b, 1), (d, c, -d*c)>。由于向量集 (d, c, -d*c) 是固定的，这本质上是模拟静止多面体与垂直于 (a, b, 1) 的移动平面的碰撞。感谢 Edelsbrunner 和 Maurer（Findingextreme points in three dimensions and solve the post-office problem in the plane，1984），有一种算法可以在时间 O(n log n) 中进行预处理，并针对不同的 a 和 b 解决这种类型的查询在 O(log n) 时间内。

一个糟糕的细节是我们必须至少选择两个区间，但最好的“解决方案”可能只是与自身最长的区间。我相信这很混乱，但可以扩展 Edelsbrunner-Maurer 以在相同的运行时间内找到第二个最极端的点。

于 2012-06-03T17:25:54.400 回答