0
$\begingroup$

I'm given a target integer range $[x, y]$ which needs to be covered $n$ times, and a stream of integer ranges $[x_i, y_i]$. I need an algorithm which consumes integer ranges from the stream and returns immediately after processing the first element which causes $[x, y]$ to be covered $n$ times.

Example:

The target range is $[0, 5]$, $n$ is $2$, and the stream contains the ranges $[0, 2]$, $[1, 5]$, $[0, 0]$, $[3, 5]$, $[0, 2]$. The algorithm should return after processing the 4th element $[3, 5]$, because the first four ranges are the minimum required to cover $[0, 5]$ twice.

My initial idea here is to process the stream one item at a time and keep track of three variables:

  • k: The number of times the target range has already been covered using the items processed so far
  • uncovered: The list of sub-ranges that need to be covered in order to finish the next covering of the target range
  • pending: A queue of sub-ranges that have been cached and not yet processed.

For each element in the stream, we search uncovered to see if the element can cover any of the uncovered sub-ranges. If not, we add the element to pending. Otherwise, we cover as many uncovered sub-ranges as we can with the element, update uncovered, and add any "unused" portions of the element to pending.

Each time we complete a covering of the target range, we increment k, and then make one pass over pending in order to complete as much of the next covering as possible using the cached sub-ranges before continuing to consume new elements from the stream.

Is there a more optimal algorithm here? Or, are there tweaks / improvements to my algorithm that can be made in order to make it more efficient? For example, it's not quite clear to me how to search or update uncovered efficiently. Perhaps I can store the sub-ranges in a binary tree instead of a list?

$\endgroup$
0
$\begingroup$

I would suggest a different approach. I suggest building a data structure that maps from an integer $v$ to the number of times that $v$ has been covered by the intervals seen so far. You should be able to build this data structure easily using any balanced binary search tree, where the leaves are intervals that all map to the same number.

Then, when a new interval arrives, it is easy to update this data structure (you might need to split an existing leaf or two, and then increment the counters for the leaves covered by the new interval). In this way, you can process each incoming interval in $O(\log n)$ time, where $n$ is the number of intervals seen so far.

Also, at each step, you can check whether the interval $[x,y]$ has been covered the required number of times so far. This is probably easiest if you augment each internal node with the smaller of the numbers on its two children. These augmented values can be updated on-the-fly. Then checking whether $[x,y]$ has been covered the requisite number of times can be done in $O(1)$ time by checking the root of the tree. (I assume that your intervals don't contain any values outside $[x,y]$, so the root will correspond to $[x,y]$. If that is not the case, first replace each interval with its intersection with $[x,y]$, so that it doesn't contain anything outside $[x,y]$.)

$\endgroup$
3
  • $\begingroup$ For the most part this makes sense, the part I'm confused about is why the check takes $O(\log n)$? If the values are updated on-the-fly during the processing of each incoming interval, wouldn't the root node always contain the smallest number over the entire interval? So wouldn't the check take $O(1)$? $\endgroup$
    – shmth
    Dec 2 '21 at 18:10
  • $\begingroup$ @shmth, you are right. I missed that. My mistake. $\endgroup$
    – D.W.
    Dec 3 '21 at 2:20
  • $\begingroup$ I've updated my answer accordingly. $\endgroup$
    – D.W.
    Dec 3 '21 at 20:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.