判断无序区间重叠非子集是否存在无排序高效算法

不存在通用场景下时间复杂度优于O(n log n)的无排序确定性算法，来完成「判断未排序区间集合中是否存在重叠且不互为子集的区间对」的任务，你目前掌握的基于排序的O(n log n)方案已经是通用场景下的理论最优实现。

复杂度下界说明 #

这个问题的计算复杂度下界为Ω(n log n)，不存在突破该下界的通用无排序算法：

• 你要检测的目标区间对本质是交叉区间：两个区间既不完全分离，也不存在一个完全包含另一个的关系。
• 该问题可以和经典的元素唯一性问题、区间重叠检测问题做线性时间归约，而这两个问题在代数决策树计算模型下的下界就是Ω(n log n)，不存在通用的线性时间解法，任何声称完全不需要排序、且能在通用场景下线性时间解决该问题的算法都不成立。

受限场景下的类无排序方案 #

只有在区间端点的值域存在明确限制时，你可以不用显式的比较排序完成检测，但这类方案本质是借助值域映射实现了非比较排序，适用范围非常窄：

• 当所有区间端点都是取值范围落在[0, M]的整数，且M的规模远小于n log n时，可以用差分数组+线性扫描的方式检测：遍历所有区间更新差分计数，扫描前缀和的同时维护当前覆盖段的端点极值，即可判断是否存在交叉区间，时间复杂度为O(n + M)。
• 若接受随机化数据结构，可以用动态插入线段树/区间树的方式逐次插入区间并检测冲突，平均时间复杂度接近线性，但最坏情况时间复杂度会退化到O(n²)，且实现过程中本质维护了有序的端点结构，不属于完全无排序的方案。

最优排序实现参考 #

你当前使用的排序方案可以优化到非常简洁的实现，核心逻辑是按左端点升序、同左端点按右端点降序排列后，单次遍历维护已遍历区间的最大右端点即可完成检测，参考代码如下：

def has_crossing(intervals):
    if len(intervals) < 2:
        return False
    intervals.sort(key=lambda x: (x[0], -x[1]))
    current_max_r = intervals[0][1]
    for l, r in intervals[1:]:
        if l < current_max_r:
            # 左端点落在已覆盖范围内，若右端点超出当前最大右边界则为交叉
            if r > current_max_r:
                return True
        else:
            # 区间完全不重叠，更新最大右边界
            current_max_r = r
    return False

内容的提问来源于stack exchange，提问作者steve p.