5

给定两个列表，每个列表包含 N 个区间（数轴的子集），每个区间都有起点和终点的形式。一个列表中有多少对这些区间包含另一个列表中的区间？

例如：

如果列表 A 是{(1,7), (2,9)}并且列表 B 是{(3,6), (5,8)}

那么 A 的区间包含 B 中的区间的对数将是 3 对：

(1,7),(3,6)
(2,9)(3,6)
(2,9)(5,8)

目标是为 O(n log n) 射击。

我目前的算法是先按 x 坐标排序并将其作为一个列表。然后按 y 坐标对列表进行排序，并计算两个列表之间的倒数。但我的问题是为什么这行得通？任何见解将不胜感激。

我目前正在可视化的方式是以下几何方式（其中线的每个交点都是 num 反转的计数）：

在此处输入图像描述

注意：我不确定如何检查列表列表中的反转。只是试图获得一种可以给出 O(n log n) 的方法。如果有任何其他方法很高兴听到建议。

4

2 回答 2

2

我将回答第一个问题，即为什么反转解决方案有效。首先，我要澄清一件事。您不应该计算所有反转（线的交叉点），而只计算发生在 A 列表中的元素和 B 列表中的元素之间的那些。在您的示例中没有区别，但我们假设A = {(1,7), (2,5)}and B = {(3,6), (5,8)}。如果我们在您的示例中将这些情况可视化，则将有 2 个交集，但我们正在寻找的只有一对，即 (1,7)、(3,6)。

现在让我们假设我们有 2 个区间：I1=(x1,y1)和I2=(x2,y2)。I2包含在I1. 这意味着x1 <= x2和y1 >= y2。现在，如果您按 x 对间隔列表进行排序，那么I1将始终是 before I2。类似地，如果您按 y 对间隔列表进行排序，那么I1将始终在 之后I2。它还表明，如果我们在第一个列表中连接, 在I1第二个列表中，则线必须交叉。I2I1I2

但是，让我们假设x1 <= x2和y1 < y2。现在I1将I2在第一个和第二个列表中。如果我们将I1,I2在第一个列表中与I1,I2在第二个列表中连接，那么这些线将永远不会交叉。同样的情况是如果 x1 > x2和y1 >= y2

以下是这些案例的可视化：

于 2016-02-08T09:15:34.600 回答
2

如果您决定也尝试树/网格方法，我将解释它是如何工作的。对于您的任务，您不需要 2D，而是需要一维区间图甚至网格。让我们选择网格，因为它更清晰。

假设您的对是从 1 到 100 的整数。那么您可以拥有一个大小为 100 的数组。数组中的每个单元格都包含空集（有序列表）。见下图：

在此处输入图像描述

现在我们开始在网格中添加间隔。我们在 1,7 和 2 之间的所有网格单元格中添加 1，在 2,9 之间的所有网格单元格中添加 1（1,2 是我们在每个插入间隔增加 1 的 ID，以这种方式插入效率低，但可以修复）。

现在我们如何检查 B 的间隔？我们只是从第一个单元格中获取每个 ID 并检查它是否也在第二个单元格中。由于单元格是集合，因此检查需要 O(log n)。在最坏的情况下，我们需要 n O(log n) 次操作来检查来自 B 的一个区间在 A 内部的重叠区间计数。

这可以扩展为使用区间图而不是网格（如果数字不是小整数）。此外，如果您在 A 中有固定数量的间隔，并且没有内存要求，那么如果我们用数组替换集合，O(logN) 可能会变成 O(1)。

于 2016-02-08T08:06:51.907 回答