快速检测多时间段重叠的数据结构及isOverlap方法实现

优化思路 #

有比暴力O(n²)更高效的解法，核心思路是排序+单次遍历，整体时间复杂度可以降到O(n log n)，适合绝大多数静态批量检测的场景：

1. 首先将所有时间段按start属性升序排序
2. 排序后仅需依次比对相邻的两个时间段：由于后面的时间段起始时间一定不早于前面的所有时间段，只要当前时间段的start早于前一个时间段的end，就可以判定存在重叠，直接返回结果即可

边界情况处理 #

• 当传入集合元素数量≤1时，不可能存在重叠，直接返回false
• 时间段端点重合的场景（比如前一个end等于后一个start）默认判定为不重叠，如果业务需要判定为重叠，把比较逻辑的isBefore改成isBefore || isEqual即可

代码实现 #

import java.util.ArrayList;
import java.util.Comparator;
import java.util.Set;
import java.time.LocalDateTime;

class Period {
      LocalDateTime start;
      LocalDateTime end;
}
 

boolean isOverlap(Set<Period> periods) {
    // 元素不足两个不可能重叠
    if (periods == null || periods.size() <= 1) {
        return false;
    }
    // 转成列表后按start升序排序
    ArrayList<Period> periodList = new ArrayList<>(periods);
    periodList.sort(Comparator.comparing(p -> p.start));
    // 遍历比对相邻元素
    for (int i = 1; i < periodList.size(); i++) {
        Period current = periodList.get(i);
        Period pre = periodList.get(i - 1);
        // 当前时间段的开始早于前一个时间段的结束，说明重叠
        if (current.start.isBefore(pre.end)) {
            return true;
        }
    }
    // 遍历完没有重叠
    return false;
} 

扩展场景说明 #

如果你需要的是动态插入时间段、同时频繁做重叠检测的场景，可以使用区间树（Interval Tree） 数据结构，单次查询和插入的时间复杂度可以控制在O(log n)，但实现复杂度远高于排序遍历方案，静态检测场景不需要使用。

内容的提问来源于stack exchange，提问作者yurii.pitomets