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.
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
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?