是的，有可能。

我们将借用典型的计算几何“扫描线”技巧。

首先，让我们回答一个更简单（但密切相关）的问题。相反，报告有多少其他的时间间隔每个区间包含的，让我们报告中的每个多少时间间隔 包含在
。因此，对于只有两个时间间隔的示例，时间间隔的I0 = [1,4]值为零，因为它包含在零个时间间隔中，而I1 = [2,3]由于值为零，因为它包含在一个时间间隔中。

您将在一分钟内看到（a）为什么这个问题更容易，以及（b）它如何导致原始问题的答案。

为了解决这个问题更容易：采取一切开始 和结束 点-所有的A 我和b 我 -并把它们放到主列表。将该列表的每个元素称为“事件”。因此，事件将类似于“间隔I
37开始”或“间隔I 23结束”。

对事件列表进行排序并按顺序进行处理。

在处理事件列表时，请保持“活动间隔”的集合S。如果遇到开始事件但没有结束事件，则该间隔为“活动”；也就是说，如果我们在此间隔内。

现在，每当我们看到结束事件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的间隔我 <一个我到在开始我在b处，伸展到无穷大，换到负无穷大，并且结束我。

对于任何间隔I j = [a j，b j ]，将Complement（I j）定义为间隔[b j，a j
]。（例如，间隔[2，3]从2开始并在3结束；因此Complement（[2,3]）= [3,2]从3开始，延伸到无穷大，环绕到-无穷大，并结束于2.）

当且仅当Complement（J）包含Complement（I）时，观察间隔I包含间隔J。（证明这一点。）

因此，我们可以通过在所有间隔的补集上运行“简单算法”来回答您的原始问题。也就是说，使用包含 所有 间隔的“活动间隔”的集合S在-
infinity处开​​始扫描（因为所有补码都包含infinity / -infinity）。使S按终点（即补码的起点）排序。

对所有起点和终点进行排序，并按顺序进行处理。当您遇到间隔I j（= [a j，b j ]）的起点时，您实际上正在达到补数的终点…因此，从S中删除I
j，查询S以查看其端点数（即补码起点）位于b j之前，并将其报告为I j的答案。如果以后遇到I
j的终点，则遇到其补码的起点，因此需要将其重新添加到活动间隔的集合S中。

由于与“简易算法”相同的原因，该最终算法为O（n log n）。

[更新]

一项澄清，一项更正，一项评论…

澄清：当然，必须增加“自平衡二叉树”，以便每个子树都知道它包含多少个元素。否则，您将无法回答“有多少个元素小于x？”。这种扩充很容易维护，但并非每个实现都提供。据std::set我所知，例如C
++ 不会。

更正：您 不 希望将任何元素重新添加到活动间隔的集合S中； 而是
将任何元素重新添加到活动间隔的集合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-无穷大，a i
]没有环绕的意思，而不是用间隔来回环绕。逻辑仍然有效，但处理过程更加清晰：首先处理所有“无论-无限”项（即终点），然后处理其他（即起点）项。

进行此更正后，我可以肯定我的解决方案确实有效。我认为，这种表述还扩展到了在一个输入中同时具有正常间隔和“向后”间隔的情况。

注释：这个问题很棘手，因为如果必须 枚举 每个间隔中包含的所有间隔的集合，则输出本身可以为O（n ^
2）。因此，任何可行的方法都必须以某种方式计算间隔，甚至无法识别它们：-)。