给定数百万个价格范围的数据集，我们需要找到包含给定价格的最小范围。
以下规则适用：
示例：
给定以下价格范围：
搜索价格7的结果应该是5-10
搜索价格100的结果应该是100-120（包含 100 的最小范围）。
实现这个的最有效的算法/数据结构是什么？
在网上搜索，我只找到了在范围内搜索范围的解决方案。
我一直在研究莫顿计数和希尔伯特曲线，但不知道如何在这种情况下使用它们。
谢谢。
因为你没有提到这个 ad hoc 算法，所以我将把这个作为你问题的简单答案：
这是一个 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类：保存树并可以查询的树：
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))
生成不连贯区间的预处理
（我将源段称为范围，将结果段称为区间）
对于范围边界（开始和结束）制作元组：（值，开始/结束字段，范围长度，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)
这样的方法怎么样。因为我们只允许嵌套而不是部分嵌套。这看起来是一种可行的方法。
(left,val)和(right,val)对。vals左/右关系对它们进行排序。high-low然后将查询的值与您所在节点的值进行比较，然后像以前一样根据该搜索左右搜索。举个例子;
我们会(l,10) (l,20) (l,30) (r,45) (r,60) (r,100)在搜索时说，65 you drop on (r,100)so you go left and can't find a point with a (l,x)such that x>=65so you go left until you get balance left and right and first right and last left is your interval. 在搜索时，我们会说 65 you drop on so you go left and can't find a point with a 这样所以你往左走，直到你左右平衡，第一个右边和最后一个左边是你的间隔。再处理部分会很长，但因为你会保持这种状态。它仍然O(n)处于最坏的情况。但最坏的情况要求你将所有东西都嵌套在彼此内部，然后寻找最外层。