时间戳

首页 > 解决方案 > 几个区间范围的快速交集？

matlab - 几个区间范围的快速交集？

问题描述

我有几个变量，所有这些都是数字范围：（行中的间隔）

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) 的交集。

您对此有何看法？是否有具有解决此问题的工具的算法/库？

我正在考虑使用某种几何方法来解决这个问题：基本上，如果我认为我的区间是一维空间中的段，那么我想要的输出将是三个段（来自三个变量）相交的点。我不确定这在算法上是否有效。建议？

标签： matlabintervals

解决方案

O(N lg N) 方法：

  1. 将每个区间 (t_A, t_B) 转换为一对标记端点 ('begin', t_A), ('end', t_B)

  2. 按时间对所有端点进行排序，这是最昂贵的步骤

  3. 进行一次遍历，跟踪嵌套深度（如果标签是“开始”则增加，如果标签是“结束”则减少）。这需要线性时间。

    • 当深度从 2 变为 3 时，就是输出间隔的开始。
    • 当它从 3 变为 2 时，它是一个区间的结束。

推荐阅读