固定时长区间最大重叠查找：活动出席率最大化算法优化咨询

针对500人规模、1个月时间跨度的调度场景，直接用差分数组+批量统计的方案就能解决，时间复杂度仅为O(N*k + M)，远低于你之前实现的O(n³)，最坏场景下运行耗时也能控制在毫秒级。 #

核心思路 #

你之前踩的两个坑本质都是方法适配错了：

• O(n³)的滑动窗口是逐次遍历每个时间点、再逐人校验是否冲突，冗余计算太多
• 参考的单点重叠计数法，本身是算“某一个时间点最多人有空”，但你要的是“某一段固定长度的时间，全程最多人有空”，规则不匹配
  这个方案的核心是把逐人逐窗口校验的冗余操作，替换为差分数组的批量区间计数，完全消除重复计算：
• 计算规则和需求完全匹配：只要活动的完整时间段落在某参与人的任意空闲区间内，就算该人可以出席
• 把所有时间转换为固定粒度的数值索引，用差分数组快速统计每个合法起点的可出席人数

具体实现步骤 #

1. 统一时间粒度与预处理 #

首先把所有可调度范围、参与人的忙碌/空闲区间，统一转换为从可调度范围起点开始的固定粒度偏移量，比如选1分钟、15分钟为粒度（粒度越粗，计算越快）。
额外补全参与人的空闲区间边界：在可调度范围的起点之前、终点之后补上“全忙”的边界，方便切割出所有符合要求的空闲段。

2. 差分数组批量计数 #

• 初始化一个长度等于「所有合法活动起点槽位数」的差分数组，初始值全为0。
• 遍历每个参与人的所有空闲区间：
  • 如果某段空闲区间的长度小于活动的固定时长，直接跳过
  • 找出这段空闲区间内，所有能放下完整活动的合法起点范围[s_valid, e_valid]
  • 对差分数组做一次区间加操作：diff[s_valid] +=1，diff[e_valid +1] -=1，代表这段范围内的所有活动起点，都能让这个参与人计入出席名单。

3. 前缀和计算找最优解 #

对差分数组做前缀和计算，每个位置的前缀和值就是“以这个时间为活动起点时，可全程出席的总人数”，遍历找到数值最大的位置，就是最优活动时间。 #

关键边界细节 #

• 所有时间区间统一按左闭右开规则处理，比如[9:00,10:00)代表9点整到10点整忙碌，10点整即刻恢复空闲，避免端点的计数错误。
• 如果存在多个并列最大出席数的时间点，可以根据业务规则加排序权重（比如优先选工作时间中点、优先选更早的时间）。
• 粒度选择可以根据业务调整：如果不需要精确到分钟，换成15分钟为粒度可以进一步降低计算量。

参考实现伪代码 #

# 基础参数配置
ACTIVITY_DURATION = 120 # 活动固定时长，单位：分钟
SCHEDULE_WINDOW_START = 可调度范围最早时间戳
SCHEDULE_WINDOW_END = 可调度范围最晚时间戳
TIME_SLOT_STEP = 1 # 每个时间槽的粒度，单位：分钟

# 计算合法的活动起点总槽位
valid_slot_count = (SCHEDULE_WINDOW_END - SCHEDULE_WINDOW_START) // TIME_SLOT_STEP - ACTIVITY_DURATION // TIME_SLOT_STEP
diff = [0] * (valid_slot_count + 2)

for person in attendee_list:
    # 把个人忙碌区间转换为左闭右开的相对偏移区间
    busy_intervals = 转换忙碌区间到相对槽位
    # 切割得到所有可放下活动长度的空闲区间
    free_intervals = 切割空闲区间(总可调度槽位范围, busy_intervals)
    for free_start, free_end in free_intervals:
        free_len = free_end - free_start
        if free_len < ACTIVITY_DURATION // TIME_SLOT_STEP:
            continue
        # 这个空闲段内的合法活动起点范围
        valid_start_low = free_start
        valid_start_high = free_end - (ACTIVITY_DURATION // TIME_SLOT_STEP)
        diff[valid_start_low] += 1
        diff[valid_start_high + 1] -= 1

# 计算前缀和找最大值
current_attend = 0
max_attend = -1
best_start_slot = 0
for slot in range(valid_slot_count):
    current_attend += diff[slot]
    if current_attend > max_attend:
        max_attend = current_attend
        best_start_slot = slot

best_activity_start = SCHEDULE_WINDOW_START + best_start_slot * TIME_SLOT_STEP

性能验证 #

按最坏场景计算：

• 1个月按22个工作日、每天8小时可调度时间计算，总可调度槽位（按1分钟粒度）为10560个
• 500个参与人，每人平均10个忙碌区间，总区间操作量仅为500*10=5000次
• 整体运算量不到2万次，内存占用不到100KB，完全不会出现性能瓶颈。

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