问题标签 [interval-tree]

令 T 为给定的区间树（大小为 n），i 为区间。令 k 为 T 中与 i 重叠的区间数。我需要找到一种算法来在时间 O(min(n, k log n)) 中列出所有这些。

给你两个区间列表，A和B。

在A中，区间按其起点排序。A没有重叠的区间。

同样，在 中B，区间按其起点排序。B没有重叠的区间。

返回两个列表之间重叠的间隔。

例子：

返回：

我在一次采访中得到了这个，被难住了。

我想比较两个列表之间的间隔。如果两者之间存在重叠，请将重叠添加到结果列表中。然后，我以较小的起始间隔推进列表的指针，但在采访结束时无法找到可行的解决方案。

解决此问题的最佳方法是什么？

给定A和B，它们是两个区间列表。A里面没有重叠，里面A也B没有重叠B。在A中，区间按其起点排序。在B中，区间按其起点排序。如何合并两个区间列表并输出不重叠的结果？

一种方法是连接两个列表，按起点排序，并应用https://www.geeksforgeeks.org/merging-intervals/中讨论的合并间隔。有没有更有效的方法？

这是一个例子：

输出：

假设我有一个x带有数字的列表，以及另一个y带有其他数字的列表。的元素y应该是 的元素x，但由于测量中的噪声，它们有点不同。对于 的每个值，我想找到最接近它y的值。x

我可以用一些循环来做到这一点，并检查每个元素y[i]，哪个元素x[j]最小化abs(x[j]-y[i])，但我很确定有一种更简单、更清洁的方法来做到这一点。列表可能很大，所以我在这里寻找有效的代码。

到目前为止我写的代码是：

但我不知道是否有更有效的方法来做到这一点......

编辑：

由于我的无知，我忘记根据收到的评论澄清一些可能相关的内容。

• 这x列表已排序
• x是唯一可以具有相当大尺寸的列表：通常在 500,000 到 1,000,000 个元素之间。y通常会非常小，少于 10 个元素。

我正在研究区间树的实现，我想知道是否可以使用红黑树而不存储最大值并使用以下伪代码？

在一个超区域 S 内，有 k 个小的子区域。k 最大可以达到 200。子区域之间可能存在重叠。我有数百万个区域 S。

对于每个超级区域，我的目标是找出其中有 2 个或更多非重叠子区域的所有组合。

这是一个例子：

超级区域：1-100

次区域：1-8、2-13、9-18、15-30、20-35

目标：

组合1：1-8、9-18

组合2：1-8、20-35

组合3：1-8、9-18、20-35

组合4：1-8、15-30

...

假设区间列表可能是 [[1,3],[2,4],[6,12]] 并且查询时间 T = 3。上述列表中为 3 的区间数为 2（即） [[1,3]，[2,4]]。是否可以在 O(logn) 时间内做到这一点？

我目前正在学习的区间树对于每个节点都有以下数据结构：

• key: 所有区间端点的中位数
• left, right: 指向左右子树
• intervals：包含区间的区间列表key。

可以在此链接中找到更准确的信息。

我了解到使用区间树进行查询的时间复杂度为 O(logn + k)，其中 n 是区间数，k 是报告结果的数量。

我不太明白这logn部分。假设v为区间树中的当前节点，Q为查询区间。该算法将是这样的：

似乎首先if我们可能需要进入两个子树。那么是不是最坏的情况下我们可能不得不遍历所有的树节点，使得时间复杂度为 O(n + k)？

我有一个排序间隔列表和另一个列表，它描述了每个间隔的索引。这是一个例子：

间隔 = [(0, 2), (2, 3), (4, 6)] // (0, 2) 包含 0，但不包含 2

值 = [2, 3, 7]

现在，我想知道，“提及”每个间隔的频率。当它的值在另一个区间时，提到了一个区间。问题是，当一个区间被提及 n 次时，它所提及的所有区间也被提及 n 次。默认情况下，所有间隔都被提及一次。所以，(4, 6) 被提到了一次，(2, 3) 也被提到了一次，但是 (0, 2) 被提到了两次，因为它的索引 2 在区间 (2, 3) 中。我想在此示例中将列表 [2, 1, 1] 作为输出。请注意，列表中的值始终在增加，并且间隔只能在其上方提及间隔。

我已经有了一个解决方案，但它的时间复杂度是 O(n**2)，这对我来说太慢了。现在有没有人是线性或 O(n*log n) 解决方案？

计算具有一些操作条件的最大重叠间隔数：

1. 插入一个区间：O(logN)
2. 删除一个区间：O(logN)
3. 计算（最大重叠区间数）：O(1)

我认为这个问题可以通过使用 avl 树（适用于插入和删除操作）来解决，但我不知道如何设计 avl 树来满足计算操作的要求。

编辑：示例：[开始，结束）

输入：[1,2),[3,4),[1,6),[3,6),[6,7)

输出：3