从该集合中选择两个区间的快速算法

Question

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

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

实际上,原始问题需要我们选择(N> = 2)个区间数,但我认为我们可以证明最优解只包含两个区间:

如果最佳解决方案有三个或更多间隔:

[                     ]
            [               ]
                   [                          ]

我们可以看到,如果我们删除中间间隔,权重不会减少.

Answer 1

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

对间隔端点集进行排序，并按升序遍历它。如果存在平局，请先考虑最左边的点，然后再考虑最右边的点。跟踪一组间隔，当您看到其最左边的点时将间隔添加到该组中，并在看到其最右边的点时从该组中删除间隔。

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