优化多区间全重叠判断算法 解决二分法求聚众最短时间的时间超限问题

性能瓶颈定位 #

• 原有实现的checkoverlap函数采用双重循环遍历所有区间对，时间复杂度为O(n²)，当输入规模较大时操作量会指数级增长，最终触发时间超限
• 该逻辑除效率偏低外无功能层面错误，但运算量无法适配大输入场景

区间重叠判断的O(n)优化方案 #

核心判定规则：一组闭区间存在公共重叠部分的充要条件为，所有区间的最大左端点 小于等于 所有区间的最小右端点

• 单次遍历所有生成的可达区间，同步维护两个关键极值：
  1. 所有区间左端点的最大值max_left
  2. 所有区间右端点的最小值min_right
• 遍历完成后仅需做一次比较：若max_left <= min_right，则说明存在公共重叠区间，即当前给定时间可满足所有人汇聚的要求
• 该逻辑时间复杂度为O(n)，相比原有实现运算效率提升两个数量级

优化后完整代码 #

people = int(input())
peoplel = [list(map(int, input().split())) for _ in range(people)] # people[i][0] 为初始位置，people[i][1] 为移动速度

def checkoverlap(intervals):
    max_left = -float('inf')
    min_right = float('inf')
    for l, r in intervals:
        max_left = max(max_left, l)
        min_right = min(min_right, r)
    return max_left <= min_right

def good(time):
    # 生成每个人在指定时间内可抵达的坐标区间
    intervals = [[p - time * v, p + time * v] for p, v in peoplel]
    return checkoverlap(intervals)

# 二分搜索定位最小满足条件的时间
low, high = 0, 10**18
precision = 1e-6
while high - low > precision:
    mid = (low + high) / 2
    if good(mid):
        high = mid
    else:
        low = mid

print(round(high, 6))

进一步优化点 #

• 合并可达区间生成与重叠判断逻辑，无需单独生成完整的区间列表，减少临时内存占用与循环次数
• 根据题目要求的输出精度调整二分收敛阈值，避免无意义的循环计算

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