遍历非重叠区间的算法

Question

我有一个排序的非重叠区间列表（从零开始，半开），例如

{[0, 5), [10, 20), [35, 40)}

假设我在其中一个区间中有一个点（例如，在本例中为 3）和步长值为 +10（即向右移动 10 个位置）。有没有一种算法可以在 O(1) 时间内计算出我的最终位置？（编辑：也许我应该说，比 O(n) 更好的东西）

未包含在区间内的数字被认为是不存在的位置，因此在上述区间上具有步骤 +10 的位置 3 将导致最终位置 19（+1 将我的位置移动到 4，然后剩余的 +9 从位置 10 开始到位置 19）。另一个例子是，如果我们将位置 15 作为起点，步长值为 -10，那么我们的最终位置将是 0.

为了简单起见，我们还可以假设最终位置总是在其中一个区间结束。然而，我们可能知道也可能不知道我们应该从哪个间隔开始计数。

我当然可以在 O(n) 时间内遍历间隔列表（n = 间隔数）。但我觉得应该有更好的方法来解决这个问题。

P.S。这个问题有名字吗？感觉应该有个合适的名字，但是不知道是什么。

Answer 1

You can easily get to logarithmic time by arranging your intervals into a binary tree (a non-leaf node should expose both the smallest covering interval for its subtree, and the actual sum of widths)

所以，稍微改变一下你原来的间隔集，

{[0, 5), [15, 20), [25,30), [35, 40)}

会被表示为像

这样的树

               {cover:[0,40), size:20}
              /                       \
{cover:[0,20), size:10}  {cover:[25,40), size:10}
      /           \              /           \
{[0,5), 5} {[15,20), 5}  {[25,30), 5} {[35,40), 5}

其中cover为覆盖子树的最小区间，size为不包括间隙的区间宽度

因此，为了处理您的 3 + 10 案例，我们会执行以下操作：

正则二叉树搜索寻找包含3的区间（对数时间）
我们正在向右移动（正步），并且此间隔涵盖该方向的 5-3=2。 2<10，所以我们还没有完成：调整剩余距离（10-2=8）并在树中向右移动。

当前节点是我们parent的左边child，所以就是看右边child下一个
这个间隔涵盖 5<8，所以我们还没有完成。调整剩余距离(8-5=3)，再次在树中向右移动

当前节点是我们parent的右边child，所以这意味着上一层，在本例中是我们grand[=65=的右边child ]
这个区间涵盖了10>3，所以我们的终点就在这里的某个地方。然而，这不是叶子，所以我们需要再往下走，从左边child开始。请注意，parent/child 范围重叠，因此我们不会在此步骤中消耗任何剩余距离。
这个区间覆盖了5>3，所以我们终于找到了右叶区间。我们的终点是 25+3 = 28.

请注意，虽然遍历权看起来是线性的，但如果有中间子树的话，我们可以跳过。它不太清楚，但应该仍然是对数的。

遍历非重叠区间的算法

Algorithm for walking over non-overlapping intervals

algorithm

intervals