algorithm - 从区间列表的子集中找到最小值和最大值

Question

给定间隔列表(此处显示了它们的索引):

0: 1,3
1: 0,4
2: 5,7
3: 6,9
4: 2,8

然后给定列表索引中的任意输入和输出，是否有一种好方法可以从包含的对应区间中确定最小值和最大值？

例如:0,4 将为您提供 0,9。 2,3 会得到 5,9。

我当前的解决方案涉及遍历范围内的每个间隔，在入点上保持最小值，在出点上保持最大值。想知道是否有算法技术的数据结构我忽略了当间隔列表很长时使它更快。由于间隔列表没有改变，也许我可以预先创建一些模型来以不同方式表示数据？

Answer 1

一种简单的方法是使用树结构。树的根将具有整个列表的最小/最大值。然后它将有两个 child ，它们给出前半部分和后半部分的最小值/最大值，等等。这将允许您拥有一个 O(log(n)) 搜索算法，其中 n 是整个间隔列表的大小。

首先你构建树。这可以通过将间隔列表分成两部分并为每个子间隔创建一棵树来递归完成:

def makeTree(begin,end,intervals):
  if end==begin:
    return None
  if end==begin+1:
    return Node(begin,end,intervals[begin],None,None)
  partition=(begin+end)/2
  left=makeTree(begin,partition)
  right=makeTree(partition,end)
  range=combineRanges(rangeOf(left),rangeOf(right))
  return Node(begin,end,range,left,right)

一旦你有了树，你就可以将树的根传递给这个函数:

def findRange(node,begin,end):
  # If the node's range doesn't intersect the range you are looking for, 
  # then you don't have to look any deeper.
  if node is None or begin>=node.end or end<=node.begin:
    return None
  # If the node's range is completely inside the range you are looking for, then
  # you also don't need to look any deeper.
  if begin<=node.begin and end>=node.end:
    return node.range
  # Otherwise, check each child.
  left_range=findRange(node.left,begin,end)
  right_range=findRange(node.right,begin,end)
  # And return the combined result.
  return combineRanges(left_range,right_range)

请注意，我使用的是半开区间，这样区间中的任何 x 的开始 <= x < 结束。这只会让代码更简洁一些。