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

假设有N个区间,将它们表达为,其中下标i位于区间

为了判定这组区间中是否存在两个区间是有重叠的,首先对这组区间进行排序,使得对于排序后的每一个区间而言,都有(这里的i小于N-1)。

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

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

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

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

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