EDIT: I posted this question to http://cstheory.stackexchange.com/questions/4358/covering-a-set-of-intervals , which looks like a more appropriate venue for such a question.
Hello, I'm trying to determine if the following problem is in P or NP: given a collection of $n$ open intervals $(s_i, t_i)$ having integer endpoints, is it possible, for given integers $k$ and $L$, to find a subset $S$ of these intervals that are "exactly" covered (i.e., the symmetric difference is a finite set of points) with $k$ closed intervals of length $L$, with each of these $k$ "covering intervals" only covering one of the given intervals at a time?
For example, given the four intervals $(0,3), (2,4), (3, 6), (3, 8)$ with $k=2$ and $L=4$, we find that $(0,3)$, $(2,4)$, and $(3,6)$ can be exactly covered by the two intervals $[0,4]$ and $[2,6]$. I hope I've stated this clearly. One thing I've tried is a reduction via the subset-sum problem, but the fact that I'm dealing with intervals complicates it in a way I'm not comfortable with. Thanks!