最快的算法确定范围重叠

本文关键字：范围 重叠 算法 | 更新日期: 2023-09-27 17:58:37

我有两组范围，每个范围是一对表示开始和结束的整数。确定两个范围之间是否有重叠的最快方法是什么？

谢谢。

最快的算法确定范围重叠

如果它们都是按开始排序的，你只需检查两个集合中的第一个范围，看看它们是否重叠，如果没有移动到集合中末端偏移最小的下一个项目，冲洗并重复，直到你发现重叠或你在一个集合的末尾。如果已经排序，这将是O（n），否则是O（n-logn）。

let，

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

我会编写以下算法：

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

这里有一个linq查询，它将返回重叠的点。这将被linq:简化为单个循环

from s1 in set1
join s2 in set1
on s1.end < s2.start || s2.end < s1.start
select Tuple.Create(s1,s2);
相关文章：