计算包含另一个间隔的间隔数？

Question

给定两个列表，每个列表包含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）的方法。如果有其他方法很高兴听到建议。

Answer 1

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

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

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

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

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