我建议你将所有内容拆分为不重叠的基本区间,以便每个基本区间要么完全覆盖给定区间,要么完全在其外部。 然后,您可以创建从基本区间到给定区间的映射。 由于基本区间不重叠,您可以使用二分搜索轻松地找到匹配项。 从那里,您可以查找映射到它的实际区间。
初始排序是O(N log N),构建映射是O(N),最终查找是O(log N),因为有二分搜索。 基本区间的数量小于2 * N。
这是一个粗略的实现。 不确定搜索点恰好击中结束区间的情况。
class IntervalFinder():
elem_list = []
elem_sets = []
def __init__( self, intervals ):
a = sorted( intervals )
b = sorted( intervals, key=lambda x : x[1] )
ia = 0
start = a[0][0]
current = set()
for xb in b:
while ia < len(a) and a[ia][0] < xb[1]:
stop = a[ia][0]
if stop > start:
self.elem_sets.append( set( current ) )
self.elem_list.append(start)
start = stop
current.add( a[ia] )
ia += 1
if start < xb[1]:
self.elem_sets.append(set(current))
self.elem_list.append(start)
start = xb[1]
current.remove( xb )
self.elem_sets.append(set())
self.elem_list.append(start)
def find( self, a ):
k = bisect.bisect( self.elem_list, a ) - 1
if k<0:
return set()
if a == self.elem_list[k]:
h = set(self.elem_sets[k])
return h.union( self.elem_sets[k-1] )
else:
return self.elem_sets[k]
intervals = [ ( 1, 10), (5, 15), (10, 20), (5, 30) ]
ifind = IntervalFinder(intervals)
for x in [0, 4,5,9,10,11, 20, 25, 30, 35]:
print( x, ifind.find(x) )
find_regions(regions, x)
会返回[(10, 20), (22, 30)]
? - Bach23
属于区间(10,20)
? - Bach