最快的算法确定范围重叠。

Question

我有两组范围，每个范围都是一对整数表示起始和结束位置。确定两个范围是否存在重叠的最快方法是什么？

谢谢。

- Mavershang

---

这些范围本身是不相交的吗？ - H H

你是从外部获取集合吗？还是可以为范围集保留自己的数据库？ - Yochai Timmer

你可以在这个链接中看到我的答案：http://stackoverflow.com/a/16961719/1534785 - Jeyhun Rahimov

Answer 1

如果两个集合都按照起始位置排序，您可以检查两个集合中的第一个范围，看它们是否重叠，如果没有，则移动到具有最小结束偏移量的集合中的下一项，反复执行此操作，直到找到重叠或到达其中一个集合的末尾。如果已经排序，时间复杂度为O(n)，否则为O(n log n)。

- BrokenGlass

Answer 2

让我们来翻译一下：

创建一个位向量，其长度为最大结束点减去最小起始点（或者为简单起见，假设它从0到最大结束点）。

将每个范围设置为起始点和结束点之间的一组位，即

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

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

这些范围重叠，如果...

e1mask & e2mask != 0

- Davinc

Answer 3

我会编写以下算法：

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

- alex

---

“Range”对象定义在哪里？ - dotnetster

你可以根据自己的喜好来定义它。它至少需要一个开始和一个结束属性。 - alex

一些有意义的参数名称会非常有帮助。 - Boris Callens

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

- Waters

---

注意循环。我不会将范围与自身进行比较，而只会将每个范围与其他范围进行一次检查。 - Waters

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

- Charles Lambert