如何得到两个值域的重叠值域

本文关键字：两个 重叠 何得 | 更新日期: 2023-09-27 18:08:38

我有以下范围在间隔[1-15]

我想找到人与人之间的重叠范围1 &2 .

Person1 [1,3] [5,10][2,4] [8,15]

这里我应该得到一个range的列表，它们是[2,3]，[8,10]。

到目前为止我发现的是通过person1的范围循环，然后是person2的范围，然后是每个范围的每个元素，然后使用条件测试。这个解不满足我，因为它是O(n)元素的范围越大，我的算法就会对每个范围内的每个元素进行循环如果我想看到这些范围

之间的嵌段，这就会花费时间

Person1:(100000;150000]和[90000;140000]。Person2:(105000;[11万]和[13万];140050]

请注意，在我的代码中，一个范围是用

表示的:
public class Range{
    public int Start {get;set;}
    public int End {get;set;}
}

那么找出重叠范围最有效的方法是什么呢?

如有任何帮助，不胜感激。

PS:这里有类似的问题如何在python中找到范围重叠?但是我不懂python代码

如何得到两个值域的重叠值域

对范围的开始和结束进行排序。保持信息，无论是一个范围开始或结束…对于您的示例，您将得到以下内容:

1 start
2 start
3 end
4 end
5 start
8 start
10 end
15 end

现在循环这些点并保留一个计数器。+1表示开始-1表示结束。此计数器表示任何时候重叠段的数量。如果您想要边界，则需要在每次增加或减少计数器时进行测试。如果你把它从1增加到2，这是一个重叠范围的开始。当您将计数器从2减少到1时，重叠范围将结束

马丁

看一下归并排序算法的归并步骤。如果对每个人的范围进行排序，这种方法可以很容易地用于计算重叠部分。

Loop
   Get the range that starts next (R1)
   if the next range of the other person (R2) starts before R1 ends
      Add the range from begin of R2 and min( end of R1 end of R2 ) to results
   Increase the counter for the person which gave you R1

如果已知您的范围是非相邻的(即，如果在两个连续范围之间总是至少有一个数字)。解决方案也将是。否则，您可能需要一个额外的压缩步骤，以确保相邻的范围将被放入一个范围。

好处是，这适用于任何有序类型，而不仅仅是整数，你可以非常快地相交任意数量的范围(O(n+m))

感谢您的澄清。

public static IList<Range> GetListIntersections(IList<Range> rangeList1, IList<Range> rangeList2)
{
    var intersection = new List<Range>();
    //add intersection of each range
    foreach (var x in rangeList1)
    {
        foreach (var y in rangeList2)
        {
            var intersect = GetIntersection(x, y);
            if (intersect != null)
            {
                intersection.Add(intersect);
            }
        }
    }
    //remove ranges that are subsets of other ranges
    intersection.RemoveAll(x => intersection.Any(y => y != x && y.Start >= x.Start && y.End <= x.End));
    return intersection;
}
public static Range GetIntersection(Range range1, Range range2)
{
    int greatestStart = range1.Start > range2.Start ? range1.Start : range2.Start;
    int smallestEnd = range1.End < range2.End ? range1.End : range2.End;
    //no intersection
    if (greatestStart > smallestEnd)
    {
        return null;
    }
    return new Range { Start = greatestStart, End = smallestEnd };
}

我不明白你是如何循环'person1的范围，然后通过person2的范围' -我不确定这意味着没有看到代码。

我看不出你怎么能得到比O(n)更好的，但是你只能迭代一次这个范围。更好的数据结构可能是bool[]或BitArray。

var person1 = new bool[15] { /* set values */ };
var person2 = new bool[15] { /* set values */ };
var overlap = new bool[15];
for (int i = 0; i < 15; i++)
{
    overlap[i] = person1[i] && person2[i];
}
相关文章：