# Name or algorithm for this line segment covering problem

Is there a name or algorithm (besides the naive one) for the following problem. I searched with keywords "line segment covering" but I couldn't make any use of the algorithms I found.

By the naive algorithm I mean the algorithm which first sorts $S$ in ascending order by $x_i$ and then sums up the distances between segments $[x_i,y_i]$.

Inputs:

• interval $I :=$ [$a$,$b$], $a,b \in \mathbb{Q}$
• set of intervals $S := \{[x_i,y_i] | i=1,...n, x_i,y_i \in \mathbb{Q} \}$

One can assume that $I \cap [x_i,y_i] \neq \emptyset$.

Output: Overall length of the sub intervals of $I$ which are not covered by $S$.

For example, if $I=[0,5]$ and $S=\{[1,2], [4,20]\}$ the algorithm outputs $3$ ($=|[0,1[|$ + $|]2,4[|$)

-
This SO question about nearly the same problem did not turn up anything smarter, nor any fancy name for the naive algorithm you describe. –  Henning Makholm Jan 19 '12 at 21:26
Thanks for the reference. I need to implement this in a database query. Now that I know there probably isn't better algorithm I can concentrate on optimizing the implementation. –  anonymous Jan 20 '12 at 6:33