代码之家 › 专栏 › 技术社区 › amit

发现多个间隔之间的重叠

interval-tree binary-tree algorithm

amit · 技术社区 · 15 年前

假设我有一个间隔(或范围)列表(例如10-15、5-7、9-12…)。问题是要找到重叠范围的子集。我当然可以用 Interval tree 为此。

我遇到的实际问题是有多个范围。最好用一个例子来解释:

在上述情况下,在第二范围的(1)和(2)之间以及在第三范围的(3)和(1),(2)之间存在重叠。

基本上,我需要找到 全部的 项目列表之间的重叠。

也许我可以用3个单独的间隔树来找出答案。有更好的办法吗?

2 回复 | 直到 8 年前

Seb 15 年前

你可以只构建一个包含所有间隔的间隔树。您只需跟踪间隔属于哪个范围,例如:

{
  int range;
  int intervalFrom;
  int intervalTo;
}

您可以将该结构放在间隔树中,并检查是否重叠。当你得到有问题的区间时,你就可以知道每个区间属于哪个区间。

Devashish Das 8 年前

间隔[a0,b0]和[a1,b1]重叠iff min(b1,b0)>max(a1,a0)

推荐文章

Ash · 递归列表拆分和索引

2 年前

Tuna ArÄ±yÃ¼rek · “结构对象*对象”和“对象*对象”之间的区别

2 年前

Zevvysan · 为什么我的打印函数之一要删除节点?

6 年前

codingBoy · 使用python进行二叉树修剪[postorder方法不起作用]

6 年前

user9573040 · 递归二叉树高度

6 年前

Dipesh Desai · 在二叉树haskell中搜索值

6 年前

Yuki.kuroshita · 从二叉树中删除节点及其所有子节点,而不使用树数据结构

6 年前

MMelvin0581 · 为什么在我的LinkedBinaryTree实现中只添加根目录

6 年前

Shuklaswag · 为什么我们要通过堆而不是二进制搜索树进行排序?

6 年前

ibrahim · “main”已停止工作-C++[开发人员++]

6 年前