最近我遇到了一个有趣的问题：
给定两个区间列表，找出这两个列表中所有重叠区间的总数。
Example
L1: ([1,2][2,3][4,5][6,7])
L2: ([1,5][2,3][4,7][5,7])
[1,5] overlaps [1,2] [2,3] [4,5]
[2,3] overlaps [1,2] [2,3]
[4,7] overlaps [4,5] [6,7]
[5,7] overlaps [4,5] [6,7]
total = 3+2+2+2 = 9
很显然暴力的方法是可行的，但速度太慢了（我需要比O(n^2)更好的方法）。
我也在这里找到了一个类似的问题（链接）。但它并不完全相同……
非常感谢任何帮助。
尝试查找扫描线算法，它将为您提供最快的解决方案。
您可以在TopCoder网站上查看简短描述，或观看Robert Sedgwick的视频。这些描述了一些更难的问题，但应该能够给您提供解决自己问题的方法。
实际上，主要思想是每次在排序后的段开始和结束列表上移动，同时更新特殊相交列表中的段列表。
对于此任务，您将分别拥有两个交集列表。在开始时，两个交集列表都为空。当到达段的开头时，将其添加到适当的交集列表中，并且显然与另一个交集列表中的所有段相交。到达段的结尾时，只需从交集列表中删除它。
这种算法将为您提供O(n log(n))的速度，并且在最坏情况下需要O(n)的内存。
制作两个已排序的列表，其中每对都有（值; +1或-1表示间隔开始和结束）。
两个计数器 - Count1和Count2，显示第一个和第二个列表中活动间隔的数量。
以合并方式遍历两个列表。
当从第一个列表获得带有+1的对时-将 Count1 增加
当从第一个列表获得带有-1的对时-将 Count1 减小，并将 Count2 添加到结果中
同样适用于来自第二个列表的对
最后阶段的伪代码
CntA = 0
CntB = 0
Res = 0
ia = 0
ib = 0
while (ia < A.Length) and (ib < B.Length)
if Compare(A[ia], B[ib]) <= 0
CntA = CntA + A[ia].Flag
if (A[ia].Flag < 0)
Res = Res + CntB
ia++
else
CntB = CntB + B[ib].Flag
if B[ib].Flag < 0
Res = Res + CntA
ib++
微妙的时刻 - 比较 if Compare(A[ia], B[ib]) <= 0
我们还应该考虑标志 - 以正确处理仅触摸端点的情况，例如 [1..2][2..3]（您认为此情况为交集）。因此，排序和合并比较器都应采用类似于这样的合成值：3 * A[ia].Value - A[ia].Flag。使用这种比较方法，具有相同坐标的区间的起始位置先于终止位置。
P.S. 在 Delphi 中进行了快速测试。对于给定的数据集和其他一对数据集有效。
Delphi 代码（ideone FPC 由于泛型而无法编译）
你可以在第二个数组上循环使用std::set_intersection函数，将其与第一个数组中的每个项目进行匹配。但我不确定性能是否符合您的要求。
我最近在解决一个类似问题时偶然发现 区间树 ADT，我认为它对你很有用，无论你是否实现它。
它基本上是一棵三叉树，我用节点构建了它，每个节点包含以下内容：
在 O(n*log(n)) 时间内构建树后，查询函数（检查重叠间隔）应该是 O(log(n) + m)，其中 m 是报告的重叠间隔数量。
注意，在创建时，按间隔结束值进行排序并拆分列表应该有助于保持平衡。
O(n²)的时间复杂度，因为你需要总和，所以实际上要使用所有组合的信息，而组合的数量是n²。如果列表中有很多重复项，或者可能存在其他可以利用的模式，那么也许你可以显著减少其中一个或两个n，但仅此而已。 - MicroVirus