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

2022-01-25 00:00:00 intervals compare java jodatime

我有一个区间列表，我需要比较它们是否有重叠.

I have a list of intervals, and I need to compare them for overlaps.

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-01日期时间2 = 2014-07-01

eg. dateTime1 = 2014-06-01 dateTime2 = 2014-07-01

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

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

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

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

在这种情况下，第二个和第三个间隔之间存在重叠.我可以使用 Interval.overlaps 方法来找到它.我正在考虑 2 个 for 循环并遍历列表中的每个间隔进行比较.但该解决方案是 O(n*n).有什么更有效的方法来做到这一点?

In this case, there is an overlap between the 2nd and the 3rd interval. I can use the Interval.overlaps method to find that. I'm thinking of 2 for loops and going through each of the intervals in the list to compare. But that solution is O(n*n). What is a more efficient way to do this?

推荐答案

你应该先按开始时间排序升序，然后只应用一个for循环 找出哪些区间是重叠的.

You should first sort the intervals by start time in ascending order and then apply only one for-loop to find out which intervals are overlapping.

使用单个 for 循环解决方案时，您需要比较两个相邻间隔是否重叠.当然，您还必须检查循环的范围条件，以注意每次循环运行时考虑两个间隔.像这样的东西(未测试):

When using the single for-loop-solution you need to compare TWO neighbour intervals if they overlap or not. Of course you have to check the range condition of the loop, too, to pay attention for that you consider two intervals per single loop run. Something like this (not tested):

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;
}

相关文章