Fastest algorithm determines range overlap

Question

I have two sets of range, each range is a pair of integers indicating the beginning and end. What would be the fastest way to determine if there is any overlap between the two ranges?

Thanks.

Answer 1

If both of them are sorted by start, you can simply check the first range in both sets, see if they overlap, and if you don’t go to the next element in the set with the smallest end offset, rinse and repeat until you find the overlap or you are at the end one set. It will be O (n) if it is already sorted, O (n log n) otherwise.

Answer 2

let

r1 = {s1, e1}
r2 = {s2, e2}

create bit vector

max (e1, e2} - min {s1, s2}
(or to simplify, suppose it is from 0 to max (e1, e2))

define each range as a set of bits between the beginning and the end, i.e.

e1mask = ((0x1<<(e1-s1))-1)<<s1; e2mask = ((0x1<<(e2-s2))-1)<<s2; 

these ranges overlap if

 e1mask & e2mask != 0 

Answer 3

I would write the following algorithm:

 bool Overlap(int s, int e, int s1, int e1) { if(s > s1 && s < e1) return true; if(s1 > s && s1 < e) return true; return false; } int[] overlaps(Range[] ranges) { List<int> res = new List<int>(); foreach(Range r in ranges) { foreach(Range rr in ranges) { if(Overlap(r.start, r.end, rr.start, rr.end)) res.add(r.start); } } return res.ToArray(); } 

Answer 4

 private static bool Overlap(Range a, Range b) { if (a.Start >= b.Start && a.Start <= b.End) { return true; } if (b.Start >= a.Start && b.Start <= a.End) { return true; } return false; } private static bool CheckOverlap(List<Range> ranges) { for (var i = 0; i < ranges.Count - 1; i++) { for (var j = i + 1; j < ranges.Count; j++) { if (Overlap(ranges[i], ranges[j])) { return false; } } } return true; } 

Answer 5

Here is a linq query that will return overlapping points. This will be reduced to a single linq loop:

 from s1 in set1 join s2 in set1 on s1.end < s2.start || s2.end < s1.start select Tuple.Create(s1,s2);