How to prove if there is no intervall overlaps?

Question

I have to implement if there is no intervall overlap.

The Intervalls look like that:

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

Right now the intervalls are stored seperately in an arraylist with min(0,100,200,500...) and max(100,200,500...)

If I add a new Intervall I have to check if there is no overlap to the existing intervalls. ex.:

250-280 is ok 300-600 is not ok

However, I have no idea how to do that?

I would use the apache IntRange solution provided [here](http://stackoverflow.com/questions/8368682/how-can-i-represent-integer-intervals-in-java) — PbxMan, Nov 10 '12 at 15:58
If you're inserting (x', y'), search on min(x(1),x(2),...,x(n)) until you find x(m),x(m+1) such that x(m) <= x' < x(m+1). Then you should check if y' < y(m), if it satisfies, it doesn't overlap, so it's ok. — nullpotent, Nov 10 '12 at 16:01
[Here](http://stackoverflow.com/a/11189080/823393) is an implementation of an `IntervalTree`. — OldCurmudgeon, Nov 10 '12 at 17:33

score 5 · Accepted Answer · answered Nov 10 '12 at 15:54

5

You can use an interval tree data structure for this task, and add elements only if there is no collisions / intersections in the interval.

answered Nov 10 '12 at 15:54

amit

175,853
27
231
333

Using a data structure suited for the query at hand is almost always the right solution. – eh9 Nov 10 '12 at 16:00

score 1 · Answer 2 · answered Nov 10 '12 at 15:51

For interval (a,b)

1 Loop your list

2 if a falls inside one of the intervals, the interval overlaps.

3 find between which two intervals a should ge

4 repeat with b. Again if b is inside any interval it overlaps.

5 if a and b are between the two same intervals they do not overlap. Otherwise they overlap.

And, of course, Yob's advice of using a single arraylist with the interval managed as an object is a good idea to do before beginning the algorithm.

score 1 · Answer 3 · answered Nov 10 '12 at 15:58

1

Right now the intervalls are stored seperately in an arraylist with min(0,100,200,500...) and max(100,200,500...)

so ...

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

But I'd probably create my own class like others have suggested.

answered Nov 10 '12 at 15:58

NimChimpsky

46,453
60
198
311

Giving the code makes sense in "I have done this program and I get this unexpected error", but not in "I do not which algorithm use". – SJuan76 Nov 10 '12 at 16:05

score 0 · Answer 4 · answered Nov 10 '12 at 15:50

You probably did create an Interval Object containing the start and end, that you are putting in your ArrayList.

You can easily implement a method on this Class that can detects a collision:

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

Now before inserting you iterate over you collection and call the hasCollision() methods... I you want to optimise the results, you can also make the Interval object implement Comparable and use a Sorted collection.

score 0 · Answer 5 · answered Nov 10 '12 at 16:37

Since intervals do not overlap, you can keep them sorted by, say, the lower bound. To find if given interval overlaps with some existing one, you can use binary search, this way searching time would be log(N).

I suggest to create class Interval implements Comparable<Interval>, and to use java.util.TreeMap<Integer, Interval>. The key is the sum of lower and upper bounds. When inserting new Interval i, check overlapping with only two entries: map.floorEntry(i.key()) and map.lowerEntry(i.key()).

score 0 · Answer 6 · answered Nov 10 '12 at 20:21

You can sort them by starting point e.g. in a 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.

This operation is O(ln N)

score 0 · Answer 7 · answered Jan 16 '14 at 22:04

0

There is a simple method as a utility method

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

answered Jan 16 '14 at 22:04

Anshu Kumar Gupta

181
1
4

How to prove if there is no intervall overlaps?

7 Answers7