给定一行上的区域列表：
regions = [(10,25), (18, 30), (45, 60), ...] # so on so forth, regions can be overlapping, of variable size, etc.
我想知道点X属于哪个区域：
x = 23
find_regions(regions, x) # ==> [(10, 25), (18, 30)]
我天真地知道（以及我当前的实现），我们只能在O（n）中进行搜索，但是具有成千上万个区域（以及成千上万个查找点，实际上是动机）的更戏剧性的用例证明了研究一种比此方法更快的方法是合理的：
regions = [(start, end) for (start, end) in regions if start < x and x < end]
我可能会以为有人之前已经解决了这个问题，但我不确定如何最好地实现它。有什么想法吗？
这就是设计要执行的确切的作业间隔树。GooglingPython interval tree建立了一个名为Banyan的现有库来实现它们，尽管我不能说它的可靠性，而且它似乎没有得到积极开发。您也可以实现自己的间隔树。
从N个间隔列表构建间隔树的预处理时间在O（Nlog（N））中，并且与其他一些答案不同，无论间隔重叠多少，它仅占用O（N）空间。确定给定点有多少间隔的时间以O（M + log（N））为单位，其中M是包含该点的间隔数。
从PyPI页面提取的榕树间隔树演示：
>>> t = SortedSet([(1, 3), (2, 4), (-2, 9)], updator = OverlappingIntervalsUpdator)
>>>
>>> print(t.overlap_point(-5))
[]
>>> print(t.overlap_point(5))
[(-2, 9)]
>>> print(t.overlap_point(3.5))
[(-2, 9), (2, 4)]
>>>
>>> print(t.overlap((-10, 10)))
[(-2, 9), (1, 3), (2, 4)]
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句