Covering a set of intervals (I was redirected from mathoverflow in asking this)

Hello,
I'm trying to determine if the following problem is solvable in polynomial time:  given a collection of $n$ half-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 with $k$ half-open intervals of length $L$, with each of these $k$ "covering intervals" only covering one of the given intervals at any particular instant?  Put another way, by William Thurston, "given a finite set of half-open intervals, is there a subset of them so the sum of their characteristic functions can be expressed as a sum of characteristic functions of intervals of length $L$"?

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!

A clarification about "only covering one of the given intervals at any particular instant":  what I mean is that, for example, the interval $[0,5]$ could be said to cover either $(0,3)$ or $(0,4)$, but not both simultaneously.
You're right to look for a reduction from the subset-sum problem. The subset problem is to find a subset $S&#39;$ of $S$ such that $\Sigma_{s&#39; \in S&#39;} s&#39; = t$. But this can be reduced to your interval cover problem with intervals $\{(0, s) : s \in S\}$, $k = t$, $L = 1$. Therefore the interval cover problem is NP-hard.

PS Why don't you make all the intervals, input and output, half-open at the same end? That way you eliminate the finite set of points at which the sum of indicator functions is different.