The fastest algorithm determine range overlap

Question

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

Thanks.

Ruano

The ranges themselves are disjunct? – Reorientation

Are you getting the set from an outside source ? Or can you keep your own database for the sets of ranges ? – Mountie

You can see my answer in this link: https://mcmap.net/q/73151/-algorithm-to-detect-overlapping-periods-duplicate – Florenceflorencia

Answer 1

If they are both sorted by start you can just inspect the first range in both sets, see if they overlaps and if not move to the next item in the set with the least end offset, rinse and repeat till you find an overlap or you are at the end of one set. This would be O(n) if already sorted, O(n log n) otherwise.

Braasch

Answer 2

let,

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

create bit vector of

max (e1, e2} - min {s1, s2}
(or for simpliciy, assume it is from 0 to max (e1, e2) )

set each range as a set of bits between start and end, i.e

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

these ranges overlap if

e1mask & e2mask != 0

Vex

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

Parament

Where is the "Range" object defined? – Corrales

Well you can define it as you like. It needs at least a start and a end property. – Parament

some meaningful parameter names would really be helpful – Uric

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

Sigismund

Notice the loops. I don't compare a range against itself and only check each range against the others once. – Sigismund

Answer 5

Here is a linq query that would return the overlapped points. This would get reduced to a single loop by linq:

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

Upbraid