如何高效检测大量有界连续区间的重叠？

当然可以通过排序大幅优化时间复杂度，将原方案的O(n²)降低到O(n log n)，这是目前检测多区间重叠最常用的高效方法。

核心思路 #

1. 先将所有任务按开始时间升序排序（若任务开始时间相同，按结束时间升序排序也可，不影响结果）
2. 遍历排序后的任务列表，只需对比当前任务的开始时间与前一个任务的结束时间：
   • 如果当前任务的开始时间小于前一个任务的结束时间，说明两个任务存在重叠，直接返回True
   • 遍历完成后未发现重叠，返回False

优化后的代码实现 #

def has_any_clash(tasks: list[tuple[float, float]]) -> bool:
    """Check if any tasks clash, return True if clashes exist, False otherwise."""
    if len(tasks) < 2:
        return False
    # 按开始时间排序，开始时间相同则按结束时间排序
    sorted_tasks = sorted(tasks, key=lambda x: (x[0], x[1]))
    prev_end = sorted_tasks[0][1]
    for curr_start, curr_end in sorted_tasks[1:]:
        if curr_start < prev_end:
            return True
        prev_end = curr_end
    return False

复杂度对比 #

• 原方案：两两比对所有任务对，时间复杂度为O(n²)，当任务数量较多时性能急剧下降
• 优化方案：排序步骤耗时O(n log n)，遍历步骤耗时O(n)，整体时间复杂度为O(n log n)，在n较大时性能优势显著

注意点 #

原代码中的has_any_clash函数注释存在逻辑错误（注释描述的返回值与实际代码相反），优化后的代码已修正该问题。

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