找到包含点的最小范围的最有效算法/数据结构是什么？

Question

给定数百万个价格范围的数据集,我们需要找到包含给定价格的最小范围.
以下规则适用:

• 范围可以完全嵌套(即1-10和5-10有效)
• 范围不能部分嵌套(即1-10和5-15无效)

示例:
给出以下价格范围:

• 1-100
• 50-100
• 100-120
• 5-10
• 5-20

搜索价格7 的结果应该是5-10
搜索价格100的结果应该是100-120(最小范围包含100).

实现这一目标的最有效的算法/数据结构是什么？
在网上搜索,我只找到了搜索范围内范围的解决方案.
我一直在关注莫顿计数和希尔伯特曲线,但无法解决如何在这种情况下使用它们.
谢谢.

Answer 1

因为您没有提到这个临时算法，所以我将建议将此作为对您问题的简单回答：

这是一个 python 函数，但很容易理解并将其转换为其他语言。

def min_range(ranges, value):
    # ranges = [(1, 100), (50, 100), (100, 120), (5, 10), (5, 20)]
    # value = 100

    # INIT
    import math
    best_range = None
    best_range_len = math.inf

    # LOOP THROUGH ALL RANGES
    for b, e in ranges:

        # PICK THE SMALLEST
        if b <= value <= e and e - b < best_range_len:
            best_range = (b, e)
            best_range_len = e - b

    print(f'Minimal range containing {value} = {best_range}')

我相信有更有效和更复杂的解决方案（例如，如果您可以进行一些预计算），但这是您必须采取的第一步。

编辑：这是一个更好的解决方案，可能在 O(log(n)) 中，但它并不简单。它是一棵树，其中每个节点都是一个区间，并且具有包含在其内部的所有严格不重叠区间的子列表。预处理在 O(n log(n)) 时间内完成，查询在最坏情况下为 O(n)（当您找不到 2 个不重叠的范围时），平均可能为 O(log(n))。

2个类：Tree，保存树并可以查询：

class tree:
    def __init__(self, ranges):
        # sort the ranges by lowest starting and then greatest ending
        ranges = sorted(ranges, key=lambda i: (i[0], -i[1]))
        # recursive building -> might want to optimize that in python
        self.node = node( (-float('inf'), float('inf')) , ranges)

    def __str__(self):
        return str(self.node)

    def query(self, value):
        # bisect is for binary search
        import bisect
        curr_sol = self.node.inter
        node_list = self.node.child_list

        while True:
            # which of the child ranges can include our value ?
            i = bisect.bisect_left(node_list, (value, float('inf'))) - 1
            # does it includes it ?
            if i < 0 or i == len(node_list):
                return curr_sol
            if value > node_list[i].inter[1]:
                return curr_sol
            else:
                # if it does then go deeper
                curr_sol = node_list[i].inter
                node_list = node_list[i].child_list

保存结构和信息的节点：

class node:
    def __init__(self, inter, ranges):
        # all elements in ranges will be descendant of this node !
        import bisect

        self.inter = inter
        self.child_list = []

        for i, r in enumerate(ranges):
            if len(self.child_list) == 0:
                # append a new child when list is empty
                self.child_list.append(node(r, ranges[i + 1:bisect.bisect_left(ranges, (r[1], r[1] - 1))]))

            else:
                # the current range r is included in a previous range 
                # r is not a child of self but a descendant !
                if r[0] < self.child_list[-1].inter[1]:
                    continue
                # else -> this is a new child
                self.child_list.append(node(r, ranges[i + 1:bisect.bisect_left(ranges, (r[1], r[1] - 1))]))

    def __str__(self):
        # fancy
        return f'{self.inter} : [{", ".join([str(n) for n in self.child_list])}]'

    def __lt__(self, other):
        # this is '<' operator -> for bisect to compare our items
        return self.inter < other

并测试：

ranges = [(1, 100), (50, 100), (100, 120), (5, 10), (5, 20), (50, 51)]
t = tree(ranges)
print(t)
print(t.query(10))
print(t.query(5))
print(t.query(40))
print(t.query(50))