查找两个整数范围之间的重叠区域

Question

我正在用 C# 编写一个复杂的算法，其中一个步骤是比较 2 个非常大的范围列表并找出重叠区域。我已经尝试了很多方法来找到它们，但我不确定我是否涵盖了所有可能性。此外，我在这一步上的算法对于庞大的列表花费的时间太长。

示例：

范围 1 = 1-400

范围 2 = 200-600

所以当我想检查这两个范围之间的重叠时，我应该得到答案 = 200。

因为总共有 200 个数字在这两个范围之间重叠。这就是我想要的答案，我想要两个范围之间重叠的整数的确切数量。

列表示例：

列表 1：1-400、401-800、801-1200 等等...
List2 : 10240-10276, 10420 10456, 11646-11682 等等...

现在我必须将 list1 的每个范围与 list2 的每个范围进行比较，并找出 list1 的某个范围是否与 list2 的任何范围重叠，如果是，那么重叠的答案是什么？这些只是为了理解目的的示例值。

我只需要一个简单且最efficient/fast的公式来找出2个范围之间的重叠答案。我可以管理其余的循环算法。

示例公式 :

var OverlappingValue = FindOverlapping(range1.StartValue, range1.EndValue,range2.StartValue, range2.EndValue);

并且如果两个范围完全不重叠，则函数必须 return 0.

PS：我没有post我的代码，因为它真的很复杂，条件很多，我只需要一个简单的公式。

Answer 1

如果有重叠范围；它必须从最大下限到最小上限，所以只需使用那个“公式”
然后通过减去它的上限到它的下限并加一个（包括所有在内）来获得该范围内的项目数
最后，如果该数量为负，则表示范围没有重叠，因此只需获取该数量和 0 之间的最大值即可处理该情况

编辑： 哎呀 C# 不是 VB.Net

int FindOverlapping (int start1, int end1, int start2, int end2)
{
    return Math.Max (0, Math.Min (end1, end2) - Math.Max (start1, start2) + 1);
}

Answer 2

您可以尝试这样的操作：

void Main()
{
    double adStart = 1.501;
    double adEnd = 21.83;
    double bdStart = 0.871;
    double bdEnd = 56.81;

    int aiStart = 21;
    int aiEnd = 35;
    int biStart = 29;
    int biEnd = 43;

    // 20.239
    double dOverlap = FindOverlapping((int)(adStart*1000), (int)(adEnd*1000), (int)(bdStart*1000), (int)(bdEnd*1000))/1000.0;

    // 6
    int iOverlap = FindOverlapping(aiStart, aiEnd, biStart, biEnd);

    // 0
    iOverlap = FindOverlapping(20, 25, 26, 30);

    // 0
    iOverlap = FindOverlapping(20, 25, 25, 30);
}

int FindOverlapping(int aStart, int aEnd, int bStart, int bEnd)
{
    int overlap = System.Linq.Enumerable.Range(aStart, aEnd - aStart).Intersect(System.Linq.Enumerable.Range(bStart, bEnd - bStart)).Count();

    return overlap;
}

Answer 3

要使用的单行公式就是这个。

假设您有 2 个间隔： (a1, a2) 和 (b1, b2)

那么重叠区域就是：max{0, min{a2-b1, b2-a1}}

查找两个整数范围之间的重叠区域

Finding overlapping region between two ranges of integers

c#

range

.net-core

intersection