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

Question

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

例如： range1 = 1-400，range2 = 200-600。因此，当我想要检查这两个范围之间的重叠部分时，我应该得到答案= 200。因为这两个范围之间有200个数字重叠。所以这就是我想要的答案，我想要两个范围之间重叠的确切整数数量。

列表示例：

List1: 1-400、401-800、801-1200等等... List2: 10240-10276、10420-10456、11646-11682等等...

现在我必须将list1的每个范围与list2的每个范围进行比较，并找出list1的某个范围是否与list2的任何范围重叠，如果是，则是什么重叠答案？这些都是为了理解而提供的样本值。

我只需要一个简单且最有效/最快的公式来找出两个范围之间的重叠答案。我可以处理其余的循环算法。

例如公式：

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

如果两个范围完全没有重叠，则函数必须返回0。

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

- Muhammad Touseef

---

你能做400-200吗？ - Oscar Siauw

如果 range2.start < range1.end，则返回 range1.end - range2.start。 - Oscar Siauw

那么，你的解决方案是什么？ - Jeroen van Langen

在200和400之间有201个整数，但不包括200（或者您需要解释边界是包含还是排除）。 - Sehnsucht

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

Answer 1

如果存在任何重叠范围，则必须从最大下界到最小上界开始，因此只需使用该“公式”
然后，通过将其上界减去下界并加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);
}

- Sehnsucht

---

非常感谢，您给了我完全需要的东西和只需一行就能实现的完美函数，这真的很有意义。再次感谢 :) - Muhammad Touseef

这对我完全没有用。我使用了ulong数字。 start1：5388080000200 end1：5388080000299 start2：2483090000000000 end2：2483099999999999 显然，这两个范围根本不重叠，但结果是：18444266371789551916而不是0。 - Nick

@Nick：我刚在LINQpad上试了一下（用long代替int），可以正常工作。 - m_a_s

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

- William Dicks

Answer 3

可以使用一行公式：

假设您有两个区间： (a1, a2) 和 (b1, b2)

那么重叠的区域将是：max{0，min{a2-b1，b2-a1}}

- Francisco Zenteno

---

这是错误的。如果a1<b1且a2>b2，则您的公式将返回大于实际重叠的值。 如果您的范围重叠（a1<b2＆b1<a2），则重叠由min（a2，b2）- max（a1，b1）给出。 - Levasco