The fastest algorithm determine range overlap

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 ran开发者_JAVA技巧ges?

Thanks.

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.

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

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

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

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