# dynamic programming to find the minimum weight cover of the points

You are given n points p1, p2, . . . , pn on the real line. The location of pi is given by its coordinate xi . You are also given m intervals I1, I2, . . . , Im where Ij = [aj , bj ] (aj is the left end point and bj is the right end point). Each interval j has a non-negative weight wj . An interval Ij is said to cover pi if xi ∈ [aj , bj ]. A subset S ⊆ {I1, I2, . . . , Im} of intervals is a cover for the given points if for each pi , 1 ≤ i ≤ n, there is some interval in S that covers pi . In the figure below, the intervals shown in bold form a cover of the points.

The goal is to find a minimum weight cover of the points. Note that a minimum weight cover may differ from a cover with minimum number of intervals.

ps: I first tried to find the smallest interval, each time we find a valid smallest interval we remove its covered points from P[ ] until P[ ] is empty, but this algorithms can be easily prove to be wrong. Then I tried to pick the minimum ratio of weight to number of its covering points, but I do not know how to apply it into dp with memoization.

## Answers

So what we can do here is first sort all the p[] array values and also sort the intervals according to a[] i.e the left end point.

Now at each state we can have two index, the first is the index of the interval and the second is the index of the point

So at each state what we have two cases:

The first case is simple, i.e we do not select the current interval.

In the second case what we can do is select the current interval if the point lies inside, also note that if we take the current interval than we can just move the index of the point in the new state forward by the no of points we find in the current interval since they are sorted.

Pseudo code for Recursive Dynamic Programming solution using memoisation:

#define INF 1e9 int n = 100; int m = 100; int p[100], a[100], b[100], w[100], memo[100][100];//initialize memo to -1 int solve(int intervalIndex, int pointIndex){ if(intervalIndex == m){ if(pointIndex == n) return 0; else return INF; } if(pointIndex == n) return 0; if(memo[intervalIndex][pointIndex] != -1) return memo[intervalIndex][pointIndex]; //we can make 2 choices either to select this interval ao not to select this interval //if we select this interval, then we also take the points that it covers //case #1 : do not take current interval int ans = solve(intervalIndex + 1, pointIndex); if(a[intervalIndex] <= p[pointIndex] && b[intervalIndex] >= p[pointIndex]){ //i.e this point is inside curr interval //case # 2 : take current interval, and all the points it contains int index = pointIndex; for(int i = pointIndex + 1; i < n; i++){ if(a[intervalIndex] <= p[i] && b[i] >= p[i]){ index = i; }else{ break; } } ans = min(ans, solve(intervalIndex + 1, index + 1) + w[intervalIndex]); } return memo[intervalIndex][pointIndex] = ans; }

The above can be modified for real numbers easily.

The complexity of above code is O(m*n*n), but it can be reduced to O(m * n), if we just precompute the value that what is the farthest point index corresponding to an interval, so that we do not have to use the for loop inside to search for it, instead just use the precomputed value.