java - 比较列表中的间隔 (JodaTime) 是否重叠

Question

我有一个间隔列表，我需要比较它们的重叠。

List<Interval> intervals = new ArrayList<>();
intervals.add(new Interval(dateTime1, dateTime2));
intervals.add(new Interval(dateTime3, dateTime4));
intervals.add(new Interval(dateTime5, dateTime6));

例如。日期时间 1 = 2014-06-01dateTime2 = 2014-07-01

日期时间 3 = 2014-08-01dateTime4 = 2014-09-01

日期时间 5 = 2014-08-15dateTime6 = 2014-09-15

在这种情况下，第 2 和第 3 个间隔之间存在重叠。我可以使用 Interval.overlaps 方法找到它。我正在考虑 2 个 for 循环并通过列表中的每个间隔进行比较。但该解决方案是 O(n*n)。执行此操作的更有效方法是什么？

Answer 1

您应该首先按开始时间对间隔进行升序排序，然后应用仅一个 for 循环 找出哪些间隔重叠。

当使用单个 for-loop-solution 时，您需要比较两个相邻区间是否重叠。当然，您还必须检查循环的范围条件，以注意您考虑每个单循环运行的两个间隔。像这样(未经测试):

public boolean isOverlapping(List<Interval> sortedIntervals) {
  for (int i = 0, n = sortedIntervals.size(); i < n - 1; i++) {
    if (sortedIntervals.get(i).overlaps(sortedIntervals.get(i + 1))) {
      return true; // your evaluation for overlap case
    }
  }

  return false;
}