javascript - 如何找到范围之间的差距？

Question

让我们使用这个范围的例子：

const ranges = [
  [
    0,
    10,
  ],
  [
    20,
    30,
  ],
  [
    40,
    50,
  ],
];

我想找到两个范围值之间的缺失范围，例如如果输入是[-10, 60]，那么预期的输出必须是：

const islands = [
  [
    -10,
    -1,
  ],
  [
    11,
    19,
  ],
  [
    31,
    39,
  ],
  [
    51,
    60,
  ],
];

我尝试搜索“不相交的范围”和“不相交的范围”以及类似的关键字。这似乎是一个以前可以解决一百万次的问题。也许我只是使用了错误的关键字。

标签： javascriptarraysalgorithmrange

Answer 1

用于查找区间交点的主要数据结构之一是区间树。您可以通过在树上查询来构建一个区间树，ranges并跟踪输入范围与它们的交集。然后，从输入范围的左到右扫描以查找间隙。

您可以在 javascript 中找到许多区间树的实现，例如这个。