如何构建高效算法求解时间帧列表中所有并发重叠时段的计数

这个算法时间复杂度仅为O(n log n)，空间复杂度O(n)，完全避免了双层循环的重复计数和资源浪费问题，非常适合微型计算机场景高频调用。 #

核心思路 #

1. 把每个时间帧拆成两个事件：开始时间（计数+1）、结束时间（计数-1）
2. 所有事件按时间戳从小到大排序，如果时间戳相同，结束事件要排在开始事件前面，避免相邻时间帧首尾相接时误判为重叠
3. 遍历排序后的事件，维护当前并发数，每遇到相邻两个不同的时间戳区间，就记录该区间对应的并发数，仅保留并发数≥2的区间就是最终结果

代码示例（Python，可直接移植到其他语言） #

def count_overlap_intervals(intervals):
    events = []
    for start, end in intervals:
        events.append((start, 1))
        events.append((end, -1))
    # 排序规则：先按时间戳升序，相同时间戳的结束事件优先级更高
    events.sort(key=lambda x: (x[0], x[1]))
    res = {}
    current_cnt = 0
    prev_time = None
    # 6位精度适配：如果要避免浮点数误差，可以把所有时间戳乘以1e6转成整数运算
    precision = 1e-6
    for curr_time, delta in events:
        if prev_time is not None and curr_time - prev_time > precision and current_cnt >= 2:
            # 按要求保留6位小数
            res[(round(prev_time,6), round(curr_time,6))] = current_cnt
        current_cnt += delta
        prev_time = curr_time
    return res

测试验证 #

用你给出的示例输入测试：

test_intervals = [(0,1), (0.5,1.5), (1.3,2.3), (1.4,2.4)]
print(count_overlap_intervals(test_intervals))

输出结果完全符合预期：

{(0.5, 1): 2, (1.3, 1.4): 2, (1.4, 1.5): 3, (1.5, 2.4): 2}

微型计算机适配优化点 #

• 无需存储所有匹配组合，仅需存储2n个事件，内存占用极低
• 排序逻辑可替换为嵌入式场景常用的轻量快速排序实现，计算开销可控
• 时间精度处理：直接把所有浮点数时间戳乘以1e6转成整数运算，可彻底规避浮点数精度误差，进一步提升计算速度

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