计算包含另一个区间的区间数量？

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坐标对列表进行排序并计算两个列表之间的逆序对数。但我的问题是为什么这样做可以实现呢？希望能得到任何见解。我当前的可视化方式如下图所示（其中每条线的交点表示逆序对数）:

注意：我不确定如何检查列表中嵌套的列表的反转。只是试图找到一种可以在O（n log n）时间内完成的方法。如果有其他方法，欢迎提出建议。

- tattvabodha

Answer 1

如果你决定也尝试树/网格方法，我会解释一下它的工作原理。对于你的任务，你不需要二维，只需要一个一维区间映射或者网格。我们选择网格因为它更清晰。

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

（原文中有图片，此处无法展示）

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

现在我们如何检查来自B的间隔？我们只需从第一个单元格获取每个ID，并检查它是否也在第二个单元格中。由于单元格是集合，所以检查需要O(log n)。在最坏情况下，我们需要进行n次O(log n)操作以检查B中的一个间隔在A中包含多少重叠间隔。

如果数字不是小整数，则可以扩展此方法以使用间隔映射而不是网格。此外，如果您在A中有固定数量的间隔，并且没有内存要求，则可以将O(logN)替换为O(1)，例如将集合替换为数组。

- Baj Mile

---

不使用树结构能否实现这个？ - tattvabodha

是的，这就是想法。您可以使用“间隔”而不是点来工作。首先尝试在1D中找出它。您可以制作区间树而不是二叉树（集合）。然后可以使用此树以logN查找点所属的区间。 - Baj Mile

抱歉，我没有正确地阅读您的问题，您的问题不涉及二维平面上的（x，y）点。您不需要四叉树。 - Baj Mile

Answer 2

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

现在假设我们有两个区间：I1=(x1,y1)和I2=(x2,y2)。I2被包含在I1中。这意味着x1 <= x2并且y1 >= y2。现在，如果按照x对区间列表进行排序，则I1始终在I2之前。类似地，如果按y对区间列表进行排序，则I1始终在I2之后。这也意味着，如果我们在第一个列表中连接I1、I2与第二个列表中的I1、I2，那么这些线必须相交。

然而，假设x1 <= x2且y1 < y2。那么在第一个列表和第二个列表中，I1将在I2之前。如果我们在第一个列表中连接I1、I2与第二个列表中的I1、I2，那么这些线永远不会相交。如果是x1 > x2且y1 >= y2的情况也是一样的。

以下是这些情况的可视化：

- Michał Komorowski