Sub O(n ^ 2)算法用于计算嵌套间隔？

Question

我们有一个表格的间隔列表.对于每个间隔,我们想要计算嵌套在其中的其他间隔的数量. [ai, bi]

例如,如果我们有两个间隔,A = [1,4]和B = [2,3].然后计数B将0是没有嵌套间隔B; 和计数A将1作为B内适合A.

我的问题是,是否存在针对此问题的子 算法,其中间隔的数量是多少？O(n2)n

编辑: 以下是间隔符合的条件.间隔的终点是浮点数.a _i/b _i的下限是0,上限是max float的最大值.此外,存在_i <b _i的条件,因此没有长度为0的间隔.

Answer 1

对的,这是可能的.

我们将借用典型的计算几何"扫描线"技巧.

首先,让我们回答一个更容易(但密切相关)的问题.相反,报告有多少其他的时间间隔每个区间包含的,让我们每一个报告多少间隔包含在.因此,对于仅有两个间隔的示例,interval的I0 = [1,4]值为零,因为它包含在零间隔中,而I1 = [2,3]值为1则因为它包含在一个间隔中.

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

要解决这个更简单的问题:获取所有起点和终点 - 所有a _i和b _i - 并将它们放入主列表中.将此列表的每个元素称为"事件".因此,事件将类似于"间隔I ₃₇开始"或"间隔I ₂₃结束".

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

在处理事件列表时,维护一组"活动间隔".如果我们遇到了它的开始事件而不是它的结束事件,则间隔是"活动的"; 也就是说,如果我们在那段时间内.

现在,每当我们看到结束事件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的间隔_我 <A _我到在开始_我,拉伸至无穷大,换到负无穷大,并且在b处结束_我.

对于任何间隔I _j = [a _j,b _j ],将补语(I _j)定义为区间[b _j,a _j ].(例如,区间[2,3]从2开始并以3结束;因此补语([2,3])= [3,2]从3开始,伸展到无穷大,包裹到无穷大,结束于2.)

当且仅当Complement(J)包含Complement(I)时,观察该区间I包含区间J. (证明这一点.)

因此,我们可以简单地通过在所有间隔的补集集上运行"简单算法"来回答您的原始问题.也就是说,使用包含所有间隔的"活动间隔"的集合S在-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中; 事实上,这样做会导致错误的答案.例如,如果间隔只是[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).因此,任何工作方法都必须以某种方式计算间隔,甚至无法识别它们:-).