本文介绍一种时间复杂度为 o(n log n) 的优化算法，用于统计给定区间列表中所有互不重叠的无序对数量，远优于暴力 o(n²) 解法，并提供可直接运行的 python 实现与关键原理说明。
本文介绍一种时间复杂度为 o(n log n) 的优化算法，用于统计给定区间列表中所有互不重叠的无序对数量，远优于暴力 o(n²) 解法，并提供可直接运行的 python 实现与关键原理说明。
在区间处理问题中，“非重叠”指两个区间 [a, b] 和 [c, d] 满足 b 不视为重叠（因左闭右开或纯数值比较下，9 不同时属于两者）；根据示例验证，题目采用严格不相交定义：区间 I₁ = (s₁, e₁)，I₂ = (s₂, e₂) 非重叠 ⇔ e₁
暴力解法需双重循环枚举所有无序对，时间复杂度 O(n²)，当 n 较大时不可扩展。更优思路是将“全局计数”转化为“单侧贡献”：对每个区间 I = (s, e)，只统计那些完全位于其左侧（即结束位置
具体实现分三步：
- 预处理：提取所有区间的右端点（end），并升序排序，得到数组 ends；
- 二分定位：对每个区间 (s, e)，在 ends 中用 bisect_left 查找首个 ≥ s 的位置 —— 该位置值即为 结束位置严格小于 s 的区间总数；
- 累加求和：将所有区间的左侧非重叠数量相加，即得最终结果。
该方法避免了对称重复计数（如不再需要再统计“右侧非重叠”并除以 2），逻辑简洁，代码清晰：
import bisect
def count_non_overlapping_pairs(intervals):
# 去重并提取所有右端点
intervals = list(set(intervals))
ends = sorted(interval[1] for interval in intervals)
# 对每个区间，统计有多少区间结束于其开始之前
total = 0
for start, end in intervals:
# bisect_left(ends, start) 返回 ends 中第一个 >= start 的索引
# 即索引值等于 ends[0:idx] 中所有元素 < start 的个数
count_before = bisect.bisect_left(ends, start)
total += count_before
return total
# 测试用例
intervals = [(1, 8), (7, 9), (3, 10), (7, 12), (11, 13), (13, 14), (9, 15)]
print(count_non_overlapping_pairs(intervals)) # 输出: 8✅ 关键优势：
- 时间复杂度：O(n log n) —— 排序 O(n log n) + n 次二分查找 O(log n)；
- 空间复杂度：O(n)，仅需存储端点数组；
- 正确性保障：严格基于偏序关系，不依赖区间是否重叠判断逻辑，避免边界歧义。
⚠️ 注意事项：
- 本解法假设区间为元组 (start, end) 且满足 start
- bisect_left 是核心——它确保统计的是 end_i
- 若业务场景要求“端点相接视为重叠”，当前逻辑已天然支持；若需“端点相接视为不重叠”，则应将条件改为 end_i
综上，该算法以精巧的排序+二分策略，将组合计数问题降维为单点查询问题，是区间类算法设计中的经典范式，适用于调度、资源分配、时序分析等多个工程场景。
