Take the 2-minute tour ×
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.

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|improve this question
    
Since you are new to this site, please consider reading this: How to ask a homework question? In particular, you should use homework tag if your question comes from a homework. I wrote this comment because this is a basic exercise in greedy algorithms, and it sounds homework-like. –  dtldarek Jan 9 '13 at 18:29
    
@dtldarek no it's not a homework for math, but i need it for designing an algorithm. i have already written my program. but this time i want to find intervals before searching trough the set. –  Sajjad Jan 9 '13 at 18:46
    
Well, it's best to just provide some context with the question, this way the community could adjust the answer according to your needs. Cheers! –  dtldarek Jan 9 '13 at 18:59
    
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
add comment

2 Answers 2

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|improve this answer
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.