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

EN

给定一组N>2的重叠区间，假定它最大限度地使联合时间相交，则留出一个包含联合中最左边点的区间和一个包含联合中最右边点的区间。由于N>2，至少还有另外一个间隔。如果从集合中删除此间隔，则不会减小间隔的合并大小，因为您留出间隔来覆盖最左边和最右边的点。您只能通过删除间隔来增加交集的大小。因此，通过删除这个区间，你只能增加你想要达到最大化的乘积，所以在N= 2时确实可以找到最好的解决方案。

对区间的端点集进行排序，并按递增顺序遍历它。在这种情况下，考虑最左边的点，而不是最右边的点。跟踪一组间隔，当您看到它的最左边点时，向它添加一个间隔，当您看到它的最右边点时，将一个间隔从集合中移除。

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

证明了两个间隔足够了：，选择一个适当包含在另一个间隔中的间隔是没有意义的。在不失去通用性的情况下，让区间为a1，b1，. an，bn，使得a1 <.< an。如果没有一个区间正确地包含另一个间隔，那么b1 <.< bn。对于i

O(n log )-time算法：重构，问题是求区间a，b，c，d极大(d - a) * (b - c)，当区间不相交时，此积是负的。我们的算法是进行O(n log )预处理，使我们能够在O(log )时间内为每个间隔找到最佳匹配。

让我们找出a，b的最佳伴侣，做一些代数：(d - a) * (b - c) = d*b *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 (三维极值点的发现与平面邮局问题的求解，1984年)，有一种算法可以在时间上对O(n log )进行预处理，并在O(log )时间内解决不同类型的a和b的查询。

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