如何获得两个范围中的重叠范围 [英] How to get overlap range of two range

问题描述

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

I have the following ranges in interval [1-15]

我想找到的人1安培之间的重叠范围; 2。

I want to find the overlap ranges between people 1 & 2.

PERSON1 [1，3] [5,10] PERSON2 [2,4] [8,15]

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

在这里，我应该得到范围的列表是[2,3]，[8,10]。

Here I should get a list of Ranges which are [2,3], [8, 10].

我发现到目前为止是循环由PERSON1的范围，然后通过PERSON2的范围，然后为每个范围中的每个元素，然后使用条件测试。 因为它是O（n）此解决方案并不能满足我。还有更多的元素是范围，更我的算法中会持续循环的每个范围中的每个元素，这将需要时间，如果我想看到论文的切入口范围

What I've found so far is to loop by person1's range, then by person2's ranges, then for each element of each range, then using conditional test. This solution doesn't satisfy me as it's O(n). More there're range of elements, more my algo will going to loop for each element of each range and that will take time if I want to see the insection between theses ranges

PERSON1：100000; 150000]及[90000; 140000]。 PERSON2：105000; 110000]及[130000; 140050]

Person1: [100000; 150000] and [90000; 140000]. Person2: [105000; 110000] and [130000; 140050]

请注意，一个范围重新由psented在我的code $ P $：

Note that a range is represented in my code by:

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

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

So what's the most efficient way to find the overlap ranges?

任何帮助将是AP preciated。

Any help would be appreciated.

PS：有此类似的问题在python如何查找范围重叠< /一>，但我不明白的蟒蛇code。

PS: there's similar question here How to find range overlap in python? but I don't understand python code.

推荐答案

看一看归并算法的合并步骤。如果范围为每个人进行排序此方法可适应很容易地计算出的重叠。

Have a look at the merge step of the mergesort algorithm. If the ranges for each person are sorted this method can be adapted to compute the overlaps very easily.

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

如果您的范围是已知的非相邻的（即，如果始终存在之间的连续范围内的至少一个数）。该解决方案也将是。否则，你可能需要额外的压制步骤，以确保相邻的范围将被放在一个范围。

If your ranges are known to be non adjacent (i.e. if there is always at least one number between to consecutive ranges). The solution will also be. Else you might need an extra compaction step to ensure that adjacent ranges will be put into one range.

的好处是，这适用于任何类型的有序，而不仅仅是整数，并且可以相交任意数量的范围非常快的（O（N + M））。

The nice thing is that this works for any ordered type and not just ints, and you can intersect any number of ranges very fast ( O(n+m) ).

这篇关于如何获得两个范围中的重叠范围的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！