CODEWITHSUNDEEP
javaalgorithmintervals
maximus
maximus

Reputation: 11524

How to prove if there is no intervall overlaps?

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?

Upvotes: 3

Views: 546

Answers (7)

Anshu Kumar Gupta
Anshu Kumar Gupta

Reputation: 181

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

Upvotes: 0

Peter Lawrey
Peter Lawrey

Reputation: 533530

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)

Upvotes: 0

Alexei Kaigorodov
Alexei Kaigorodov

Reputation: 13535

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()).

Upvotes: 0

NimChimpsky
NimChimpsky

Reputation: 47290

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.

Upvotes: 1

amit
amit

Reputation: 178451

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

Upvotes: 5

SJuan76
SJuan76

Reputation: 24885

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.

Upvotes: 1

Frank
Frank

Reputation: 15641

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.

Upvotes: 0

Related Questions