AKJ88's blog

Maximum coverage area over a range.
By AKJ88, history, 9 years ago, In English

I am faced with a problem in real world and couldn't get the optimal solution for that.

Imagine that we have several ranges over [0..n] and we want to choose several of them in a way that cover this range in the best way possible, without intersecting with one another. A simplified version of this problem can be found in UVA-10020-Minimal coverage.

For example if n==10 we can have the following ranges to choose from:

[0..2]

[0..3]

[1..5]

[6..8]

[7..10]

And the desired answer would be [1..5] & [7..10].

Obviously greedy is not the right approach in this problem.

I would really appreciate it if someone could help me in solving this problem.

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
9 years ago, # |
← Rev. 4   Vote: I like it +3 Vote: I do not like it

Sort the intervals according to their endpoints (in ascending order). Let's call the left ends of the intervals L[i], the right ends R[i]. Let DP[i] be the optimal solution for the first i intervals in the list. Then in pseudocode, 

DP[i] = max(DP[i-1], R[i]-L[i] + DP[binarySearch(L[i] in R)])

The binary search should find the greatest index j where R[j] < L[i].

i.e. either you don't take the i-th interval and use the previous solution or you take the i-th interval and use the last solution that you can fit before it.

It might be possible to do this part in O(N) instead of O(N log N), but since we need O(N log N) for sorting anyway, I didn't try to optimize it.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for your reply, I try to implement it and ask further questions. Just one more thing, it would be great if you could explain memoization for finding the resulting ranges.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      One way could be storing whether you chose to use each interval when calculating DP[i] or not, i.e. whether DP[i-1] or the other term was greater when maximizing. Then you can scan the array backwards, and when you find an interval which was chosen, add it to the the solution list and then ignore other chosen intervals as you go on until their R[i] is smaller than the L[i] of the one you added to the solution.

      Also, something to note: be more consistent when handling the lengths than I was in the prev comment. :D Either R[i] is the last point still in the interval, in which case the length should be R[i]-L[i] + 1, or the first point after it, but then the binary search criterion is R[j] <= L[i].

      → Reply