美文网首页雕bug小技程序员
如何检查一组区间中是否存在两个区间有交集

如何检查一组区间中是否存在两个区间有交集

作者: Liutos | 来源:发表于2017-03-19 19:07 被阅读613次
    假设有N个区间,将它们表达为 ,其中下标i位于区间 中 为了判定这组区间中是否存在两个区间是有重叠的,首先对这组区间进行排序,使得对于排序后的每一个区间 而言,都有 (这里的i小于N-1)。

    为了说明要如何判定这些区间中是否存在重叠,首先我们假设这其中确实存在着至少两个这样的区间,假设分别是第j个和第k个(假设j小于k),它们必然会满足这样的关系

    这是因为如果 ,那么所有位于区间 中的数都将会小于 b_k,那么第j个区间与第k个区间就不可能有交集了,因此上述不等式一定成立。再加上这一组区间都是按照区间的下界递增排序的,那么必然有 假设

    ,由于k和j都是正整数,这意味着在第j和第k个区间之间,必然还存在着一个区间l,那么这个区间的必然满足

    这就意味着第j个区间和第l个区间也存在交集,它们的交集是子区间 (这里假设 )。这就说明了,如果可以在一组区间中找到两个不相邻的区间,它们存在重叠的部分,那么一定可以找到第三个区间,使得这个区间与其中的一个区间也存在重叠。

    这表示如果我们要判定一组区间是否存在重叠,那么只需要先将它们基于区间的起点按照递增排序后,比较每一对相邻的两个区间是否存在重叠即可。

    相关文章

      网友评论

        本文标题:如何检查一组区间中是否存在两个区间有交集

        本文链接:https://www.haomeiwen.com/subject/sclvnttx.html