# The smallest set of unit- length closed intervals that contains all of the given points

Given a set of points like this: $\{0.7, 1.0, 1.5, 2.0, 2.3, 2.6, 3.1, 3.6, 3.9, 4.2, 4.7, 5.2, 5.5 \}$ i want to creat a set of lists so that each of the lists keeps the numbers between a closed interval of length 1. for example my set of lists should be like this:
$\{[0.7, 1.0, 1.5], [2.0, 2.3, 2.6], [3.1, 3.6, 3.9], [4.2, 4.7, 5.2], [5.5] \}$
where first list keeps numbers between 0.7 to 1.7 , the second list keeps the numbers between 2 to 3 and third list keeps numbers between 3.1 to 4.1 and fourth list numbers between 4.2 to 5.2 and the fifth list the nembers between 5.5 to 6.5.
my question is how can i find the Lowest possible number of intervals for a set so that the intervals are unit length and they contain all of the given points?

-
Pick any $c$ in your set. A number $y$ is in the list of $c$ iff $|c-y|\leq 1$,so given any $c$ find all such $y$, then you have the list, now order the list. Do this over the other points no yet considered. Doesn't this work? – leo Jan 14 '13 at 8:49

You will necessarily need one interval that contains the smallest point, $0.7$, and such an interval that covers the most points is always $[0.7, 1.7]$. Discard the points that it covers, and repeat.

-

I believe the greedy algorithm will work here.

1. Let $x$ be the smallest element in your set not already put in a list.

2. Put all the elements in $[x, x+1]$ in a list.

3. Repeat, lol.

The reason why the greedy algorithm works is because consider the smallest element $x$ not yet in a list. There is no harm in using a list of $[x,x+1]$ so you might as well use it.

-