计算所有重叠时间区间的冲突数量

嘿，这个问题我之前帮不少开发者梳理过，你的思路完全找对了方向——先按startTime排序绝对是高效处理区间重叠计数的核心第一步！下面我把完整的算法逻辑拆解清楚，再结合例子和代码帮你落地：

1. 先对区间按startTime排序 #

把所有记录按startTime从小到大排序；如果两条记录的startTime相同，建议再按endTime从小到大排序。排序后我们能保证：对于任意i<j，区间i的startTime ≤ 区间j的startTime，这会大大简化后续的重叠判断逻辑。

2. 遍历排序后的区间，维护活跃区间集合统计冲突 #

这里的关键是跟踪当前还在“活跃”状态的区间——也就是那些endTime大于当前遍历区间startTime的区间（因为排序后当前区间的startTime不会比前面的小，只要前面的区间还没结束，就和当前区间重叠）。

具体步骤：

• 初始化conflictCount = 0，用来累计总冲突数
• 初始化一个有序列表activeEndTimes，专门保存当前活跃区间的endTime（维护有序是为了高效移除已结束的区间）
• 逐个遍历排序后的区间：
  1. 先清理activeEndTimes：移除所有endTime ≤ 当前区间startTime的记录（这些区间已经完全结束，不会和当前及之后的区间重叠）
  2. 此时activeEndTimes里的所有区间都和当前区间重叠，所以总冲突数加上列表的长度（每一个活跃区间都和当前区间形成一对冲突）
  3. 把当前区间的endTime插入到activeEndTimes的合适位置，保持列表有序

这种方式的巧妙之处在于：它会自动统计所有两两重叠的组合。比如三个区间全重叠时，第三个区间会和前两个活跃区间各形成一次冲突，加上前两个区间之间的一次冲突，总冲突数正好是3（对应所有两两组合），完全符合你设定的规则。

3. 实例验证 #

举几个典型场景测试逻辑：

场景1：三个区间全重叠 #

区间：A(1,5)、B(2,6)、C(3,4)

• 处理A：activeEndTimes为空，conflictCount=0，加入5后列表为[5]
• 处理B：清理后activeEndTimes仍为[5]，conflictCount +=1（总1），加入6后列表为[5,6]
• 处理C：清理后activeEndTimes仍为[5,6]，conflictCount +=2（总3），加入4后列表为[4,5,6]
  最终冲突数3，对应(A,B)、(A,C)、(B,C)三对，正确。

场景2：仅两个区间重叠 #

区间：A(1,3)、B(2,4)、C(5,7)

• 处理A：conflictCount=0，列表为[3]
• 处理B：清理后列表为[3]，conflictCount +=1（总1），列表变为[3,4]
• 处理C：清理后列表为空，conflictCount +=0（总1），列表变为[7]
  最终冲突数1，仅(A,B)一对，正确。

场景3：三个区间中仅两对重叠 #

区间：A(1,5)、B(2,3)、C(4,6)

• 处理A：conflictCount=0，列表为[5]
• 处理B：清理后列表为[5]，conflictCount +=1（总1），列表变为[3,5]
• 处理C：清理掉endTime ≤4的3，列表剩余[5]，conflictCount +=1（总2），列表变为[5,6]
  最终冲突数2，对应(A,B)、(A,C)两对，正确（B和C不重叠，不计入）。

4. 可落地的伪代码 #

这里用Python风格的伪代码实现，利用bisect模块维护有序列表，保证整体时间复杂度为O(n log n)，适合大数据量场景：

def calculate_conflict_count(intervals):
    # 按startTime排序，startTime相同则按endTime排序
    sorted_intervals = sorted(intervals, key=lambda x: (x['startTime'], x['endTime']))
    conflict_count = 0
    active_end_times = []
    
    for interval in sorted_intervals:
        current_start = interval['startTime']
        current_end = interval['endTime']
        
        # 用二分查找快速定位并移除已结束的区间
        import bisect
        idx = bisect.bisect_right(active_end_times, current_start)
        active_end_times = active_end_times[idx:]
        
        # 新增的冲突数等于当前活跃区间的数量
        conflict_count += len(active_end_times)
        
        # 将当前endTime插入有序列表
        bisect.insort(active_end_times, current_end)
    
    return conflict_count

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