我们有一个形式为 的区间列表。对于每个区间，我们要计算嵌套在其中的其他区间的数量。 [ai, bi]
例如，如果我们有两个区间，A = [1,4]并且B = [2,3]。那么 for 的计数B将是0因为 ; 没有嵌套的间隔B。并且计数A将在.1BA
我的问题是，是否存在针对此问题的子 算法，区间数在哪里？O(n2)n
编辑： 这是间隔满足的条件。间隔的端点是浮点数。a i 's/b i的下限是 0，上限是最大浮点数。此外，存在 a i < b i的条件，因此没有长度为 0 的区间。
对的，这是可能的。
我们将借用典型的计算几何“扫描线”技巧。
首先，让我们回答一个更简单（但密切相关）的问题。让我们报告每个区间包含多少个区间，而不是报告每个区间包含多少其他区间。因此，对于只有两个区间的示例，区间I0 = [1,4]的值为零，因为它包含在零区间中，而I1 = [2,3]值为一，因为它包含在一个区间中。
您将在一分钟内看到（a）为什么这个问题更容易以及（b）它如何导致原始问题的答案。
为了解决这个更简单的问题：获取所有起点和终点——所有 a i和 b i——并将它们放入一个主列表。将此列表的每个元素称为“事件”。因此，事件将类似于“间隔 I 37开始”或“间隔 I 23结束”。
对该事件列表进行排序并按顺序进行处理。
在处理事件列表时，请维护一组“活动间隔”。如果我们遇到了它的开始事件但没有遇到它的结束事件，则一个间隔是“活动的”；也就是说，如果我们在那个区间内。
现在，每当我们看到一个结束事件 b j时，我们就可以计算有多少间隔包含 I j (= [a j , b j ])。我们需要做的就是检查活动区间的集合 S 并确定其中有多少在j之前开始。这就是我们对有多少个区间包含区间 I j的答案。
为了有效地做到这一点，保持 S 本身按起点排序；例如，通过使用自平衡二叉树。
对事件列表进行排序是 O(2n log 2n) = O(n log n)。从自平衡二叉树中添加或删除元素是 O(log n)。问“自平衡二叉树有多少个元素小于 x？” 也是 O(log n)。因此，整个算法是 O(n log n)。
所以，这解决了简单的问题。称之为“简单算法”。现在看看你实际问的是什么。
将数轴视为延伸到无穷大并环绕到 -infinity，并定义一个区间，其中 b i < a i从 a i开始，伸展到无穷大，环绕到负无穷大，并在 b i结束。
对于任何区间 I j = [a j , b j ]，将 Complement(I j ) 定义为区间 [b j , a j ]。（例如，区间 [2, 3] 从 2 开始，在 3 结束；所以 Complement([2,3]) = [3,2] 从 3 开始，延伸到无穷大，回绕到 -infinity，并在2.)
观察区间 I 包含区间 J 当且仅当 Complement(J) 包含 Complement(I)。（证明这一点。）
因此，我们可以简单地通过在所有区间的补集上运行“简单算法”来回答您的原始问题。也就是说，从 -infinity 开始扫描，其中包含所有间隔的“活动间隔”集合 S（因为所有补码都包含无穷大/-无穷大）。保持S按结束点排序（即补码的开始点）。
对所有起点和终点进行排序，并按顺序进行处理。当您遇到区间 I j (= [a j , b j ]) 的起点时，您实际上是在到达其补码的终点...所以从 S 中删除 I j，查询 S 以查看其端点的数量（即补充起点）出现在 b j之前，并将其报告为 I j的答案。如果您稍后遇到 I j的终点，您将遇到其补码的起点，因此您需要将其重新添加到活动区间的集合 S 中。
出于与“简单算法”相同的原因，这个最终算法是 O(n log n)。
[更新]
一个澄清，一个更正，一个评论……
澄清：当然，必须扩充“自平衡二叉树”，以便每个子树都知道它包含多少元素。否则，您无法回答“有多少个元素小于 x？” 这种增强很容易维护，但并不是每个实现都提供。例如，据我所知，C++std::set没有。
更正：您不想将任何元素添加回活动区间集合 S；事实上，这样做可能会导致错误的答案。例如，如果间隔只是 [1,2] 和 [3,4]，您将点击 1（并从集合中删除 [1,2]），然后点击 2（并重新添加），然后点击 3 ...由于 2<4，您会得出结论 [3,4] 包含 [1,2]。这是错误的。
从概念上讲，您已经处理了补码区间的所有“开始事件”；这就是为什么 S 开始将其内部的所有间隔。所以你只需要担心终点；您永远不想向 S 添加任何元素。
换句话说，您可以将 [b i ,a i ]（其中 b i > a i）视为没有回绕的 [b i - infinity, a i ]，而不是让区间回绕。逻辑仍然有效，但处理更加清晰：首先您处理所有“任意 - 无穷大”项（即终点），然后处理其他项（即起点）。
有了这个更正，我很确定我的解决方案确实有效。这个公式也延伸——我认为——到你在一个输入中同时拥有正常和“向后”间隔的情况。
评论：这个问题很棘手，因为如果您必须枚举每个区间中包含的所有区间的集合，则输出本身可能是 O(n^2)。因此，任何工作方法都必须以某种方式计算间隔，甚至无法识别它们:-)。
这是一个 O(N*LOG(N))：
让 Ii = 区间 i = (ai, bi)
让 L = 区间列表 I
按 ai 排序 L
将 L 分成两半为 L1a 和 L2a。
按 bi 对 L1a 和 L2a 进行排序得到 L1b 和 L2b
合并排序 L1b 和 L2b 跟踪嵌套计数（例如，因为 L1b 中的所有间隔都在 L2b 中的间隔之前开始，当我们在 L1b 中找到高于 l2b 中的端点的端点时，我们知道它们之间的所有内容都嵌套在里面 -考虑一下）..
现在您已经更新了 L2 中的区间嵌套在 L1 中的区间内的频率。
在合并 L1 和 L2 之后，我们通过将 L1 划分为 L11a 和 L12a 来重复该过程（递归），还将 L2 划分为 L21a 和 L21a..