Самый быстрый алгоритм определения диапазона перекрытия

Question

У меня есть два набора диапазонов, каждый диапазон представляет собой пару целых чисел, указывающих начало и конец. Какой самый быстрый способ определить, есть ли какое-либо совпадение между двумя диапазонами?

Спасибо.

Answer 1

Если они оба отсортированы по началу, вы можете просто проверить первый диапазон в обоих наборах, посмотреть, не перекрываются ли они, и если нет, перейти к следующему элементу в наборе с наименьшим смещением конца, промыть и повторять, пока не найдете перекрытие. или вы находитесь в конце одного сета. Это будет O (n), если уже отсортировано, O (n log n) в противном случае.

Answer 2

пусть,

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

создать битовый вектор из

max (e1, e2} - min {s1, s2}
(или, для простоты, предположим, что это от 0 до max (e1, e2))

установить каждый диапазон как набор битов между началом и концом, т.е.

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

эти диапазоны перекрываются, если

e1mask & e2mask != 0

Answer 3

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 4

Я бы написал следующий алгоритм:

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 5

Вот запрос linq, который возвращает перекрывающиеся точки. Это будет сведено к одному циклу по linq:

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