Question:
Given $n$ points on the $x$-axis, We are asked to provide a dynamic programming algorithm to cover the distance between the first and the last point with $k$ closed intervals such that the conditions written below hold:
(i) The endpoints of these $k$ intervals are chosen from the given $n$ points. (For example, If $2,3,4,5$ are given, We should provide a way to cover the interval $[2,5]$. But we cannot choose the interval $[2,2.5]$ because $2.5$ is not in the given set.)
(ii) Our algorithm should guarantee that the length of the biggest interval is the minimum possible value.
(iii) The time complexity of our algorithm should be of $O(nk)$.
Note: It is valid to use intervals with length $0$.
My try:
Obviously, The first point between the given $n$ points should be one of the endpoints of one of my covering intervals. So, I should decide for the other endpoint of this interval. What I mean is I have to choose one of the remaining $n-1$ points to be the other endpoint. So, It seems like each time that I'm picking an interval, I should decide for only one of its endpoints.
But, The problem is that this method results in an algorithm of $O(n^2\times k)$ which is not enough because the question asks for $O(nk)$.
Any idea?
Thanks in advance