在重叠列表中比较间隔(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));

例如.dateTime1 = 2014-06-01 dateTime2 = 2014-07-01

dateTime3 = 2014-08-01 dateTime4 = 2014-09-01

dateTime5 = 2014-08-15 dateTime6 = 2014-09-15

在这种情况下,第2和第3间隔之间存在重叠.我可以使用Interval.overlaps方法来查找它.我想2循环,并通过列表中的每个间隔进行比较.但那个解决方案是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;
}