3

如果没有间隔重叠，我必须实施。

间隔看起来像这样：

0-100
100-200
200-500
500-1000
1000-2000 ect....

现在，intervalls 分别存储在一个带有 min(0,100,200,500...) 和 max(100,200,500...) 的数组列表中

如果我添加一个新的间隔，我必须检查现有间隔是否没有重叠。前任。：

250-280 可以 300-600 不行

但是，我不知道该怎么做？

4

7 回答 7

5

您可以为此任务使用区间树数据结构，并且仅当区间中没有碰撞/交叉点时才添加元素。

于 2012-11-10T15:54:42.017 回答
1

对于区间 (a,b)

1 循环你的列表

2 如果a落在其中一个区间内，则区间重叠。

a3 找出应该在哪两个区间

4 重复b。同样，如果b在它重叠的任何间隔内。

5 如果a和b在两个相同的区间之间，它们不重叠。否则它们会重叠。

当然，Yob 建议在开始算法之前使用单个数组列表并将间隔作为对象进行管理是一个好主意。

于 2012-11-10T15:51:57.707 回答
1

现在，intervalls 分别存储在一个带有 min(0,100,200,500...) 和 max(100,200,500...) 的数组列表中

所以 ...

bool isCollided = false;
Integer min = 250;
Integer max = 280;
for(Integer intOne: firstList){
  Integer intTwo = secondList.get(firstList.indexOf())
  if( (min >= intOne && <= intTwo) || (max >= intOne && <= intTwo){
    isCollided = true;
    break;
  }
}

但我可能会像其他人建议的那样创建自己的课程。

于 2012-11-10T15:58:30.563 回答
0

您可以按起点对它们进行排序，例如在NavigableMap中。

NavigableMap<Integer, Integer> map =
map.put(100, 200);
map.put(300, 500);

// to test for a range.
int start = 300, end = 400;
if (map.floorEntry(start).getValue() >= start && map.ceilingKey(start) <= end)
   // out of existing ranges.

这个操作是 O(ln N)

于 2012-11-10T20:21:36.607 回答
0

由于间隔不重叠，因此您可以按下限对它们进行排序。要查找给定间隔是否与某个现有间隔重叠，您可以使用二进制搜索，这样搜索时间将是 log(N)。

我建议创建class Interval implements Comparable<Interval>和使用java.util.TreeMap<Integer, Interval>. 关键是上下界之和。插入 newInterval i时，只检查两个条目的重叠：map.floorEntry(i.key())和map.lowerEntry(i.key()).

于 2012-11-10T16:37:19.987 回答
0

您可能确实创建了一个包含开始和结束的间隔对象，并将其放入 ArrayList。

您可以轻松地在此类上实现一个可以检测碰撞的方法：

public boolean hasCollision(Interval inter){....}

现在在插入之前迭代你的集合并调用 hasCollision() 方法......我想优化结果，你也可以让 Interval 对象实现Comparable并使用 Sorted 集合。

于 2012-11-10T15:50:40.407 回答
0

有一个简单的方法作为实用方法

public static boolean isOverlapping(Date start1, Date end1, Date start2, Date end2) { return start1.before(end2) && start2.before(end1); }

于 2014-01-16T22:04:35.103 回答