1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.