时间戳

首页 > 解决方案 > 检查多个周期是否重叠的数据结构

java - 检查多个周期是否重叠的数据结构

问题描述

我有一个由和日期Period表示的类，之后在哪里。我需要编写一个函数来检查周期是否重叠。startendendstart

直接的方法是检查每个周期与其他周期。有没有办法引入执行速度更快的数据结构？

class Period {
      LocalDateTime start;
      LocalDateTime end;
}
 

boolean isOverlap(Set<Period> periods) {
    // TODO put the code here
}

isOverlaptrue当至少两个周期重叠时应该返回。

标签： javaalgorithm

解决方案

每隔一个周期检查每个周期将具有 O(n 2 ) 时间复杂度。相反，我会按开始和结束时间对它们进行排序，然后遍历列表。这样，一个时期只能与它之前和之后的时期重叠（或在它之前或之后的多个后续时期 - 但这无关紧要，因为您正在寻找一个重叠来返回true）。您可以遍历列表并检查它。该算法的总成本将是排序的成本，O(nlog(n))：

boolean isOverlap(Set<Period> periods) {
    List<Period> sorted =
        periods.stream()
               .sorted(Comparator.comparing((Period p) -> p.start)
                                 .thenComparing(p -> p.end))
               .collect(Collectors.toList());
    for (int i = 0; i < sorted.size() - 1; ++i) {
        if (sorted.get(i).end.compareTo(sorted.get(i + 1).start) > 0) {
            return true;
        }
    }
    return false;
}

推荐阅读