如何获取两个范围的重叠区域

Question

我有以下区间在[1-15]范围内。

我想找到人1和人2之间的重叠范围。 Person1 [1, 3] [5, 10] Person2 [2, 4] [8, 15]

在这里，我应该得到一个列表，其范围为[2,3]，[8, 10]。

到目前为止，我发现要循环使用person1的范围，然后再使用person2的范围，然后对于每个范围的每个元素，再使用条件测试。但是，这种解决方案并不满足我的要求，因为它的时间复杂度是O(n)。如果要查看这些范围之间的交集，则范围中的元素越多，算法将循环的时间就会越长。

Person1：[100000；150000]和[90000；140000]。 Person2：[105000；110000]和[130000；140050]

需要注意的是，在我的代码中，一个范围由下面的方式表示：

public class Range{
    public int Start {get;set;}
    public int End {get;set;}
}

那么找到重叠范围的最有效方法是什么？

任何帮助都将不胜感激。

附注：这里有一个类似的问题How to find range overlap in python?但我不理解Python代码。

- John

---

你如何在不检查n个范围的情况下知道是否存在更多的重叠？ - dlev

我认为他的意思是n代表元素的范围，而不是范围的数量。例如，不需要迭代2000次并测试每个元素，就可以计算[1,1000]与[100,2000]的交集。他希望仅迭代范围（在本例中为两个范围），而不是元素（共2000个）来计算交集范围。 - hatchet - done with SOverflow

Hatchet说得对，我会编辑我的帖子，让它更清晰明了。 - John

“合并重叠区间”算法可以提供一些线索。 - RBT

Answer 1

对范围的起始和结束点进行排序。并保留是否为范围起始或结束的信息... 对于您的示例，将得到以下结果：

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

现在循环遍历这些点并计数..对于开始+1，对于结束-1。该计数器是任何时候重叠段的数量。如果您想要边界，需要测试每次增加或减少计数器的时间。如果您从1增加到2，则这是重叠范围的开始..当您将计数器从2减少到1时，重叠范围结束。

- Martin Booth

Answer 2

感谢澄清。那么像这样的东西呢...

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

- codeConcussion

---

我有一个范围的IList。我需要检索。 - John

这很简单且有效，但它的时间复杂度为O(N^2)，所以只适用于小数据集。 - tigrou

Answer 3

看一下归并排序算法的合并步骤。如果每个人的范围都已经排序，那么这种方法可以很容易地适应计算重叠。

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)）。

- LiKao

Answer 4

我不明白你是如何通过“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];
}

- Kirk Broadhurst

---

如果范围已排序，他可以遍历两个人的范围，比较他当前查看的person1的范围与person2的范围，停留在具有更高端点值的范围上，移动到具有较低端点值的person的下一个范围。这样可以在4个步骤中计算出交集，而不是15个步骤。 - hatchet - done with SOverflow

@hatchet，这是真的，但大O表示法是一个上限 - 或者说是“最坏情况”。如果“范围”像[1] [3] [5]等那样，那么比这种方法更多的步骤。两者都是O（n）。请注意，我只是建议一种更清晰的描述他的数据的方法 - 通过BitArray循环迭代非常快速。 - Kirk Broadhurst

我同意最坏情况可能有相似的成本，最坏情况是[1,1] [2,2] [3,3]...，但你的最佳和平均情况将与最坏情况相同。对于典型情况，遍历范围可能会更加高效。 - hatchet - done with SOverflow

@hatchet 你可能是对的，但我不敢假设了解典型情况。遍历范围需要两个迭代器（你需要同时遍历两个），并且需要更复杂的逻辑。这个算法的最佳情况将具有与同时遍历两个范围的最坏情况相同的“计算复杂度”，但速度更快、更简单。 - Kirk Broadhurst

感谢你的解决方案。我所指的 person1 的范围和 person2 的范围是......最好我在这里写下这个想法：http://pastebin.com/PJ905id1 顺便说一句，我不理解你的解决方案包含布尔数组......你能提供更多细节吗？ - John