我有几个变量,所有变量都是数值范围:(行间隔)
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]将是两个这样的情况.
解决这个问题的一种方法是将我的值组合在一起并将二进制文件组合在一起,但由于我的值是连续的,因此会产生"边缘效应",并且我将首先浪费时间对值进行分类.(以我想要的分辨率对我的数据集进行分类会产生数百GB的数据).
另一种不涉及分箱的方法是在所有可能的变量组合之间使用成对交叉(让我们称之为X),然后是X与所有其他变量O(n ^ 3)的交集.
你对此有何看法？是否有算法/库有工具来解决这个问题？
我正在考虑使用几何方法来解决这个问题:基本上,如果我认为我的间隔是1D空间中的段,那么我想要的输出将是三个段(来自三个变量)相交的点.我不确定这在算法上是否有效.建议吗？
O(N lg N)方法:
将每个间隔(t_A,t_B)转换为一对标记的端点('begin',t_A),('end',t_B)
按时间对所有端点排序,这是最昂贵的一步
做一遍,跟踪嵌套深度(如果标记为'start'则递增,如果tag为'end'则递减).这需要线性时间.