I came up with the following problem, but do not know how to analyze it.
Let $S$ be an ordered set of integers with size $n$ (i.e., $S=\{1,2,...,n\}$). An interval $INV(a,b)$ covers the elements in $S$ from $a$ to $b$ $(1 \leq a < b \leq n)$. For example, $INV(3,5)$ covers the element of $\{3,4,5\}$. Now I am trying to analyze the following problem:
Given a set of intervals $I$, select $k$ intervals $R$ from $I$ (i.e., $R\subseteq I$ and $|R|=k$), such that $R$ covers the most of $S$.
I am also interesting in a more generalized version where each element has a weight. But I wish to analyze the simpler version first. Specifically, I wish to know whether there exists polynomial time (wrt. $n$) for this problem. If not, is this problem NP-hard, and how to prove it ?
Any hints or discussions would be very helpful.
Thank you.
