CODEWITHSUNDEEP
algorithmrangeintervalsminimumgreedy
etnie1031
etnie1031

Reputation: 73

Develop algorithm to get minimum number of subranges needed to cover range from 1 to n

Can anyone help me out with this problem with some pseudocode and/or an explanation of how to go about solving this?

You are given a list of ranges {start, stop} and a target length n. Some of the ranges will overlap with other ranges. Develop an algorithm that determines the minimum number of ranges that are needed to fully span from 1 to n.

For example, if I am given a list of ranges [{1,2},{1,3},{2,3}] and a target length n = 3, I should return 1, because we only need {1,3} to cover from 1 to 3. Obviously, this is a pretty simple test case.

Any ideas? I'm pretty stumped. I almost wanted to develop some sort of greedy algorithm, but I'm not sure if this lends itself to a greedy solution...

Upvotes: 0

Views: 861

Answers (2)

conditionalMethod
conditionalMethod

Reputation: 167

You can use an Interval Tree. Put the intervals in the data structure.

Start with a = 1.

At each step query the tree for the interval that overlaps a and has largest right end. Observe that when you implement the interval tree as an augmented red-black tree, you can make the query gives you both of these conditions.

Reset the value of a to be the value of this right end.

Repeat while the query returns a result and each time store the resulted interval in a list that will become the answer. Stop when a >= n.

Return the list obtained.

Proof that the result above has minimum cardinality

Assume that the sequence of intervals, ordered by their left ends, obtained above is I1, I2,...,Im, and call a1, a2, ..., am, their right ends.

If J1, J2, ..., Jr were another sequence of intervals, ordered by their left ends covering [1,n] with r minimum. Call b1, b2, ..., br theirs right ends.

Note that J1 covers 1. Therefore b1 <= a1 by construction of I1. Therefore J2 overlaps I1. If J2 were inside I1, then the sequence J could be made shorter by replacing J1 and J2 with I1. This contradicts that the sequence J has minimum length.

Therefore, J2 covers a1. You can see where this is going. Now we repeat the argument above. By construction, b2 <= a2. Therefore J3 overlaps b2. If J3 were inside I1 union I2, then the sequence J could be made shorter by replacing J1, J2, J3 with I1, I2, which is a contradiction with r being minimum. Therefore, J3 covers a3. Repeat, and you end up having that r = m.

Upvotes: 0

ruakh
ruakh

Reputation: 183321

As of now, I'm thinking that i should start by sorting the list of ranges by their start element, but I'm not sure where to go next...

Yes, that's a good start.

Once you've done that, you iterate through in "chunks" of "reachable" ranges:

  • First, you scan through all the ranges where start ≤ 1 (meaning that they are immediately "reachable"), and find the greatest end among those ranges — call it max_end1.
  • Then, you scan through all the ranges with 1 < start ≤ max_end1 (meaning that you can "reach" them after only one prior interval), and find the greatest end among those ranges — call it max_end2.
  • Continue doing this until you reach some i such that max_endi ≥ n. That i is the answer.
  • If you ever reach a point where the "chunk" of reachable ranges is empty — all your ranges so far only get you up to x (where x < n), and the next range has start > x, or there is no next range — then there is no answer, because even all of the intervals taken together don't cover the range from 1 to n.

Note that, although you only iterate through the sorted list once, it will probably be simpler to implement if you use two nested loops: an outer loop to iterate over the "chunks", and an inner loop to iterate over the intervals in each "chunk".

Upvotes: 2

Related Questions