标签: interval-tree

这是一个有趣的问题:给定一组N个区间([start,end]),使用区间树来查找重叠区间的最大数量.

StackOverflow上的类似问题提供了O(N)解决方案,但是如果我们可以将区间预处理到区间树中,也许我们可以在对数时间内找到解.

实际上,Cormen等人的"算法导论"一书中的练习问题表明,这可以通过增加红黑间隔树来实现.有什么想法可以做到这一点？

我需要在Java中使用IntervalTree或RangeTree,并且无法找到具有工作删除支持的实现.

在sun.jvm.hotspot.utilities.IntervalTree中有一个内置的,但RBTree超类中的deleteNode方法指出:

/**
 * FIXME: this does not work properly yet for augmented red-black
 * trees since it doesn't update nodes. Need to figure out exactly
 * from which points we need to propagate updates upwards.
 */

尝试从树中删除节点最终会抛出异常:

节点的最大端点未正确更新

delete在sun.jvm.hotspot.utilities.IntervalTree的子类中正确实现功能有多难？或者是否有另一个Interval Tree实现已经正确实现了这个？

目前我只是在擦除树并在每次删除时重新填充它,这远非理想(注意:在RBTree中设置DEBUGGING = false会大大加快速度).

我正在寻找一种数据结构,它可以在封闭的时间间隔内有效地运行,具有以下属性:

• 动态添加或删除间隔

• 设置并随时更改每个间隔的数字("深度").没有两个深度是一样的

• 查找与任何给定间隔重叠的所有间隔,按"深度"排序

我找到的最接近的结构是Interval树,但是它以相对于它们的深度的任意顺序列出了找到的间隔.我可以收集所有报告的"未排序"间隔,然后对它们进行排序,但我跳过它可以避免为每个查询排序结果.

请问,有没有人知道这样的数据结构或有任何建议如何(如果可能的话)增强Interval树来支持这样的排序？

例:

1. 将[1,2]添加到空结构并将其深度设置为1
2. 添加[10,100],深度= 2
3. 添加[5,55],深度= 3
4. 查询[5,50]报告[10,100]和[5,55]
5. 将[10,100]的深度设置为3,将[5,55]设置为2
6. 查询[5,50]报告[5,55]和[10,100]

编辑

我对快速添加/删除和查询更感兴趣,而不是更新深度.深度可以与O(n)一样多,如果这有助于加速其他操作.

我有一个带整数值的区间列表[例如.[1,4],[10,19]等].有没有办法将这些间隔放入一些java集合的容器中[例如.设置]这样我就可以在容器上调用'union'函数.'union'函数应该给我一个间隔列表,这样如果任何2个插入的间隔重叠,那么它们应该在输出中合并.我尝试在Guava中使用Range类,但最终在合并之前将所有间隔相互比较.一个优雅的方法将非常感谢!以下是我根据以下回答尝试的内容.输出为[[1,15],[17,20]],这是正确的.我想知道是否有一些现有的API实现了这样的东西.

public static void main(String[] args) {
    // mock data
    List<MyIntRange> rng_lst = new ArrayList<Junk.MyIntRange>();
    rng_lst.add(new MyIntRange(1, 10));
    rng_lst.add(new MyIntRange(5, 15));
    rng_lst.add(new MyIntRange(17, 20));

    // sort intervals by start position
    Collections.sort(rng_lst);

    // merge the intervals which overlap
    List<MyIntRange> res_lst = new ArrayList<Junk.MyIntRange>();
    MyIntRange old_rng = null;
    for (MyIntRange cur_rng : rng_lst) {
        if (old_rng == null) {
            old_rng = cur_rng;
        } else {
            if (old_rng.rng.upperEndpoint() < cur_rng.rng.lowerEndpoint()) {
                // this does not over lap with the next one
                res_lst.add(old_rng);
                old_rng …

更新5：

此功能已作为 pandas 20.1 的一部分发布（在我生日那天:]）

更新4：

PR已合并！

更新3：

PR已经搬到这里了

更新2：

看来这个问题可能有助于在 pandas 中重新开放 IntervalIndex 的 PR。

更新：

我不再遇到这个问题，因为我现在实际上正在查询 和 的重叠范围A，B而不是B查询落在 的范围内的点A，这是一个完整的区间树问题。不过我不会删除这个问题，因为我认为这仍然是一个有效的问题，而且我没有一个好的答案。

问题陈述

我有两个数据框。

在 dataframe 中A，两个整数列一起表示一个区间。

在 dataframe 中B，一个整数列代表一个位置。

我想做一种连接，以便将点分配给它们所属的每个区间。

间隔很少但偶尔重叠。如果一个点落在该重叠范围内，则应将其分配给两个间隔。大约一半的点不会落在一个区间内，但几乎每个区间都会有至少一个点在其范围内。

我一直在想什么

我最初打算将我的数据从 pandas 中转储，并使用IntervalTree或Banyan或bx-python但后来我遇到了这个要点。事实证明，soyer 的想法从未进入 pandas，但它让我思考——也许可以在 pandas 中做到这一点，而且因为我希望这段代码能够像 python 一样快，所以我直到最后才将我的数据从 pandas 中转储出来。我也觉得这可以通过binspandascut函数实现，但我是 pandas 的新手，所以我可以使用一些指导！谢谢！

笔记

潜在相关？Pandas DataFrame groupby 可变长度的重叠间隔

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

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

我到目前为止编写的代码是:

x_in = [1.1, 2.2, 3, 4, 6.2]
y_in = [0.9, 2, 1.9, 6, 5, 6, 6.2, 0.5, 0, 3.1]
desired_output = [1.1, 2.2, 2.2, 6.2, 4, 6.2, 6.2, 1.1, 1.1, 3]

y_out = []

for y in y_in:
    aux = [abs(l - y) for l in x_in]
    mn,idx = min( (aux[i],i) for i in range(len(aux)) )
    y_out.append(x_in[idx])

>>> y_out …

给定一组N个区间:对于每个区间,哪个其他区间具有最大重叠？

例如{[0,5],[2,9],[2,3],[4,9]}:

[0,5]:[2,9](重叠4)

[2,9]:[4,9](重叠6)

[2,3]:[0,5]或[2,9](重叠2)

[4,9]:[2,9](重叠6)

N可以很大,所以我认为间隔树是必要的.但是,我发现的帖子或出版物都没有描述这种查询的方法.查询的结果可以位于间隔树节点(中心左侧,中心重叠,中心右侧)的3条路径中的任何一条路径上,因为它们可能包括也可能不包括查询间隔的中心点.因此,我无法想到获得结果的log(N)遍历方法.

另外,对于[2,3]的情况,我并不关心选择哪一个.可以任意挑选任何最大交叉间隔.每个查询只返回1个结果.

是否可以在log(N)中回答每个查询,提供Nlog(N)整体解决方案？

编辑:我编写的伪代码:

query(ITnode node, Interval intrv){
    // s_list: start-sorted intervals overlapping center
    // e_list: end-sorted intervals overlapping center
    if intrv.end < node.center:
        node_max = search node.s_list for interval w/ closest start to intrv.start
        return max(node_max, query(node.left_tree, intrv))
    else if intrv.start > node.center:
        node_max = search node.e_list for interval w/ closest end to intrv.end
        return max(node_max, query(node.right_tree, intrv))
    else: // Query overlaps center
        // Still working this out but I get the picture …

我有一组重叠的区间,我必须从相应的区间中选择一个元素,这样当它们被分组时,选择中有最小的间隙.

通过分组我的意思是连续的元素被分组.如果元素的其他区间没有连续元素,则将其视为具有一个元素的组

通过最小化差距我的意思是,我们减少了这些群体的数量,并尝试形成更大的群体

我看到间隔树和思想可能有所帮助,但不知道如何使用它为我的利益

请告诉我应该采取什么方法来解决问题.

例:

间隔(包括边界)

[1,2]
[2,4]
[3,7]
[6,11]
[9,11]
[5,11]
[10,14]
[13,14]

可能解决方案

[1,2] ==> 2
[2,4] ==> 3
[3,7] ==> 4
[6,11] ==> 10
[9,11] ==> 9
[5,11] ==> 11
[10,14] ==> 12
[13,14] ==> 13

通过选择上述元素形成的组

2,3,4 and 9,10,11,12,13

所以只有一个4到9的差距

我正在寻找一个间隔树C#集合类.

我需要能够添加间隔,理想2D,否则我可以组合两个标准1D间隔树.

我还需要能够找出与给定间隔重叠的间隔.

我发现这个intervaltree.codeplex.com但是

没有与此版本相关的下载.

编辑:

继续这里:C#使用其他代码