计算一组重叠段覆盖的总面积的算法？

Question

我有一个可能重叠区间的端点列表，我想要一种有效的方法来计算 k 个区间覆盖的总面积，对于 k=1,2,...。 (不进行所有成对比较)。或者，这不可能吗？

例如，假设x是起点列表，y是终点列表，那x[i] < y[i] , 和

x = (1.5, 2, 3, 5)
y = (3, 4, 4, 6)

使得至少一个区间覆盖的总面积为3.5，至少两个区间覆盖的总面积为1。

谢谢，ph。

Answer 1

这是一个来自计算几何的经典线扫描问题。

在每个起点加上一个+1，在每个终点加上一个-1。然后想象在数轴上从负无穷大走到正无穷大。

每次遇到 +1 时，将高度增加 1。每次遇到 -1 时，降低高度。当您在数轴上从 p1 移动到 p2 时，将 p2 - p1(扫描长度)添加到给定高度所覆盖的量。

然后您将得到每个高度恰好覆盖的长度直方图。如果您想处理“至少两个间隔”的情况，您可以累加总数。