如何高效查找首个包含至少3个事件的3年时间区间？

问题背景 #

给定一组带时间戳的事件列表（定义如下），需要找到首个包含至少3个事件的3年时间区间（比如示例中2005-2008年覆盖的区间），要求实现高效解法。

from dataclasses import dataclass
from datetime import date

@dataclass
class Event:
    start: date

events = [
    Event(date(2001, 10, 1)),
    Event(date(2002, 9, 1)),
    Event(date(2005, 8, 1)),
    Event(date(2006, 7, 1)),
    Event(date(2007, 6, 1)),
    Event(date(2008, 5, 1)),
    Event(date(2009, 4, 1)),
]

高效解法：顺序遍历验证/滑动窗口 #

因为事件时间戳天然有序（如果无序先排序），我们可以用线性遍历+时间差验证或滑动窗口实现，最优时间复杂度为O(n)（已排序），未排序则为O(n log n)（排序耗时）。

核心思路

由于事件按时间升序排列，从左到右检查每一组连续3个事件：如果第i个事件和第i+2个事件的时间差≤3年，那么以第i个事件的起始时间为起点的3年区间内，必然包含至少这3个事件，这就是我们要找的首个符合条件的区间（从左到右第一个满足条件的组就是最早出现的）。

代码实现（基础版）

from datetime import date
from dateutil.relativedelta import relativedelta  # 需安装：pip install python-dateutil

# 确保事件按时间排序（原列表无序时执行）
events_sorted = sorted(events, key=lambda e: e.start)

result_interval = None
# 遍历连续3个事件的组合
for i in range(len(events_sorted) - 2):
    current_start = events_sorted[i].start
    third_event_start = events_sorted[i+2].start
    # 用relativedelta处理闰年，计算3年后的准确日期
    three_years_later = current_start + relativedelta(years=3)
    if third_event_start <= three_years_later:
        result_interval = (current_start, three_years_later)
        break  # 找到首个区间后直接退出

if result_interval:
    print(f"首个符合条件的3年区间：{result_interval[0]} 至 {result_interval[1]}")
else:
    print("不存在包含至少3个事件的3年区间")

代码说明

1. 排序处理：先对事件按起始时间排序，保证我们能从左到右检查最早出现的事件组。
2. 精准时间计算：用relativedelta(years=3)替代timedelta(days=3*365)，自动处理闰年天数差异，结果更准确。
3. 提前终止：找到第一个符合条件的区间就立即退出循环，避免不必要的计算。

滑动窗口优化版（适配任意事件数量要求）

如果需要灵活调整所需的事件数量（比如不是固定3个），可以用双指针滑动窗口：

from datetime import date
from dateutil.relativedelta import relativedelta

events_sorted = sorted(events, key=lambda e: e.start)
left = 0
target_count = 3  # 可修改为任意需要的事件数量
result_interval = None

for right in range(len(events_sorted)):
    # 当前右指针事件的3年前日期
    three_years_ago = events_sorted[right].start - relativedelta(years=3)
    # 移动左指针，确保窗口内事件都在3年区间内
    while events_sorted[left].start < three_years_ago:
        left += 1
    # 检查窗口内事件数量是否达标
    if right - left + 1 >= target_count:
        result_interval = (three_years_ago, events_sorted[right].start)
        break

if result_interval:
    print(f"首个符合条件的3年区间：{result_interval[0]} 至 {result_interval[1]}")
else:
    print("不存在包含至少3个事件的3年区间")

这个方法同样是线性时间复杂度，适合扩展到不同的事件数量要求。

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