Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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.

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.