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

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)，而且可能是O(log(n))。

两个类:保存树并可以查询的树：

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))

Answer 2

产生分离间隔的预处理

(我称源段为范围，将结果段称为间隔)

对于永远的范围边框(开始和结束)，让元组：(值，开始/结束，范围长度，id)，把它们放在数组/列表中。

根据第一个字段对这些元组进行排序。在打领带的情况下，从左开始，右转结束。

Make a stack
Make StartValue variable.
Walk through the list:
     if current tuple contains start:
          if interval is opened:   //we close it
             if  current value > StartValue:   //interval is not empty
                  make interval with   //note id remains in stack
                      (start=StartValue, end = current value, id = stack.peek)       
                  add interval to result list
          StartValue = current value //we open new interval
          push id from current tuple onto stack
     else:   //end of range
             if  current value > StartValue:   //interval is not empty
                 make interval with    //note id is removed from stack
                      (start=StartValue, end = current value, id = stack.pop)
                 add interval to result list
         if stack is not empty:
              StartValue = current value //we open new interval

在此之后，我们对包含源范围的开始/结束值和id的不连接的间隔进行了排序(注意，许多间隔可能对应于相同的源范围)，因此我们可以很容易地使用二进制搜索。

如果我们按嵌套顺序(在父级之后嵌套)逐个添加源范围，我们可以看到每个新范围最多可能产生两个新的间隔，因此M <= 2*N的总间隔数和总体复杂度为O(Nlog N + Q * logN)，其中q是查询数。

编辑：添加了if stack is not empty部分

结果对于您的示例1-100，50-100,100-120，5-10，5-20是

1-5(0), 5-10(3), 10-20(4), 20-50(0), 50-100(1), 100-120(2) 

Answer 3

由于pLOPeGG已经讨论了特殊情况，我将在执行预处理以高效支持多个查询的前提下回答这个问题。

用于间隔高效查询的通用数据结构是区间树和段树。