区间列表中非重叠对的最优计数：求优于O(n²)的解法

问题描述 #

给定一个区间列表，需要统计其中非重叠对的数量（即两个区间无交集，满足前一个区间的右端点小于后一个区间的左端点）。示例如下：

输入区间列表：

[(1, 8), (7, 9), (3, 10), (7, 12), (11, 13), (13, 14), (9, 15)]

对应的非重叠对共有8个：

((1, 8), (11, 13))
((1, 8), (13, 14))
((1, 8), (9, 15))
((7, 9), (11, 13))
((7, 9), (13, 14))
((3, 10), (11, 13))
((3, 10), (13, 14))
((7, 12), (13, 14))

当前采用暴力解法，通过两两比较所有区间实现，时间复杂度为O(n²)，代码如下：

def count_non_overlapping_pairs(intervals):
    intervals = list(set(intervals))  # 去重
    intervals.sort(key=lambda x: x[1])
    pairs = 0
    for i in range(len(intervals)):
        for j in range(i+1, len(intervals)):
            if intervals[i][1] < intervals[j][0]:
                pairs += 1
    return pairs

询问是否存在更优的实现方案。

更优解法：O(n log n) 时间复杂度 #

当然存在更优方案，我们可以通过排序+二分查找将时间复杂度降至O(n log n)，具体思路如下：

核心思路 #

1. 去重与排序：先对区间去重，然后按区间的右端点从小到大排序。排序后，已处理过的区间的右端点会形成一个递增序列，方便后续二分查找。
2. 遍历统计：遍历每个区间时，统计有多少个之前处理过的区间的右端点小于当前区间的左端点——这些区间都和当前区间构成非重叠对。利用二分查找可快速找到该数量，避免暴力遍历。
3. 维护有序序列：由于按右端点排序，每次遍历的区间右端点都大于等于之前的，因此可直接将当前区间的右端点追加到有序列表中，无需额外排序操作。

代码实现 #

import bisect

def count_non_overlapping_pairs(intervals):
    # 去重（区间为元组，支持哈希去重）
    intervals = list(set(intervals))
    n = len(intervals)
    # 区间数量不足2时直接返回0
    if n < 2:
        return 0
    
    # 按区间右端点从小到大排序
    intervals.sort(key=lambda x: x[1])
    
    total_pairs = 0
    # 维护已处理区间的右端点有序列表
    processed_ends = []
    
    for start, end in intervals:
        # 用二分查找统计processed_ends中小于当前区间左端点的元素数量
        # bisect_left返回第一个大于等于start的位置，位置值即为小于start的元素个数
        valid_count = bisect.bisect_left(processed_ends, start)
        total_pairs += valid_count
        # 将当前区间的右端点追加到有序列表（因排序过，列表始终保持递增）
        processed_ends.append(end)
    
    return total_pairs

验证示例 #

用示例输入测试该函数：

• 排序后的区间按右端点顺序为：(1,8), (7,9), (3,10), (7,12), (11,13), (13,14), (9,15)
• 遍历每个区间时，统计的有效非重叠对数量依次为：0、0、0、0、3、4、1，总和为8，与示例结果一致。

内容的提问来源于stack exchange，提问作者Spectacles4