Algorithm for walking over non-overlapping intervals

Question

I have a list of sorted non-overlapping intervals (zero-based, half open), e.g.

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

Let's say I have a point in one of the intervals (say, 3 in this case) and a step value of +10 (i.e. move right 10 positions). Is there an algorithm that can compute my final position in O(1) time? (EDIT: maybe I should say, something better than O(n))

Numbers not covered by the interval are considered nonexistent positions, so position 3 with step +10 on the above intervals would result in a final position of 19 (+1 moves my position to 4, then the remaining +9 starts from position 10 up to position 19). Another example is if we have position 15 as the start and a step value of -10, we would then have a final position of 0.

For simplicity's sake, we can also assume that the final position always ends in one of the intervals. We may or may not know from which interval we should start counting, however.

I can of course iterate over the interval list in O(n) time (n = number of intervals). But I feel like there should be a better way to attack this.

P.S. Does this problem have a name? This feels like it should have a proper name, but I'm not sure what it is.

Can't you just use a preprocessing step to put all values in an array, and then fetch them in O(1) ? If you do this operations many times (at least Omega(n) times) then in average the cost is O(1)... — gdelab
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). I'm not sure how to get to constant time though. — Useless
@Useless Would you mind converting your comment in a more detailed answer? I'm interested in the specific details and apparently it is a correct soution. — Codor

Useless Useless · Accepted Answer · 2017-04-07T12:59:03

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)

So, altering your original set of intervals a bit,

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

would be represented as a tree like

               {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}

where cover is the smallest interval covering the subtree, and size is the interval width excluding gaps.

So, to handle your 3 + 10 case, we do something like:

regular binary tree search to find the interval containing 3 (logarithmic time)
We're moving right (positive step), and this interval covers 5-3=2 in that direction. 2<10, so we're not done yet: adjust the remaining distance (10-2=8) and move right in the tree.

The current node is the left child of our parent, so that means looking at the right child next
This interval covers 5<8, so we're still not done. Adjust the remaining distance (8-5=3) and move right in the tree again.

The current node is the right child of our parent, so that means going up a level, in this case to the right child of our grandparent
This interval covers 10>3, so our end point is somewhere in here. However, this isn't a leaf, so we need to go down again, starting with the left child. Note that the parent/child ranges overlap, so we're not consuming any remaining distance in this step.
This interval covers 5>3, so we finally found the right leaf interval. Our endpoint is 25+3 = 28.

Note that although the traversal right looks linear, we could have skipped over intermediate subtrees if there were any. It's less immediately clear, but should still be logarithmic.

Algorithm for walking over non-overlapping intervals

1 Answers