几个区间范围的快速交集？
Fast intersection of several interval ranges?
我有几个变量，都是数值范围：（行间隔）
a = [ 1 4; 5 9; 11 15; 20 30];
b = [ 2 6; 12 14; 19 22];
c = [ 15 22; 24 29; 33 35];
d = [ 0 3; 15 17; 23 26];
（我的真实数据集中的值不是整数，但为了清楚起见在这里表示为整数）。
我想找到至少 3 个变量相交的区间。在上面的例子中 [20 22] 和 [24 26] 就是两个这样的例子。
解决这个问题的一种方法是对我的值进行分箱并将分箱加在一起，但由于我的值是连续的，这会创建一个 'edge effect'，我会浪费时间对值进行分箱第一名。 （以我想要的分辨率对我的数据集进行装箱会创建数百 GB 的数据）。
另一种不涉及分箱的方法是在所有可能的变量组合之间使用成对交集（我们称之为 X），然后使用 X 与所有其他变量的交集 O(n^3)。
您对此有何看法？ algorithms/libraries 有解决这个问题的工具吗？
我正在考虑使用某种几何方法来解决这个问题：基本上，如果我认为我的间隔是一维的线段 space，那么我想要的输出将是三个线段（来自三个线段）的点变量）相交。我不确定这在算法上是否有效。有什么建议吗？
O(N lg N) 方法：
将每个区间 (t_A, t_B) 转换为一对标记端点 ('begin', t_A), ('end', t_B)
按时间对所有端点进行排序，这是最昂贵的一步
遍历一次，跟踪嵌套深度（如果标签为'start'则递增，如果标签为'end'则递减）。这需要线性时间。
- 当深度从 2 变为 3 时，它是输出间隔的开始。
- 当从3变为2时，一个区间结束。
我有几个变量，都是数值范围：（行间隔）
a = [ 1 4; 5 9; 11 15; 20 30];
b = [ 2 6; 12 14; 19 22];
c = [ 15 22; 24 29; 33 35];
d = [ 0 3; 15 17; 23 26];
（我的真实数据集中的值不是整数，但为了清楚起见在这里表示为整数）。
我想找到至少 3 个变量相交的区间。在上面的例子中 [20 22] 和 [24 26] 就是两个这样的例子。
解决这个问题的一种方法是对我的值进行分箱并将分箱加在一起，但由于我的值是连续的，这会创建一个 'edge effect'，我会浪费时间对值进行分箱第一名。 （以我想要的分辨率对我的数据集进行装箱会创建数百 GB 的数据）。
另一种不涉及分箱的方法是在所有可能的变量组合之间使用成对交集（我们称之为 X），然后使用 X 与所有其他变量的交集 O(n^3)。
您对此有何看法？ algorithms/libraries 有解决这个问题的工具吗？
我正在考虑使用某种几何方法来解决这个问题：基本上，如果我认为我的间隔是一维的线段 space，那么我想要的输出将是三个线段（来自三个线段）的点变量）相交。我不确定这在算法上是否有效。有什么建议吗？
O(N lg N) 方法：
将每个区间 (t_A, t_B) 转换为一对标记端点 ('begin', t_A), ('end', t_B)
按时间对所有端点进行排序，这是最昂贵的一步
遍历一次，跟踪嵌套深度（如果标签为'start'则递增，如果标签为'end'则递减）。这需要线性时间。
- 当深度从 2 变为 3 时，它是输出间隔的开始。
- 当从3变为2时，一个区间结束。