# greedy algorithm on set cover

If I'm covering the interval [0,1] with sets which are themselves closed intervals, is there a covering where the greedy algorithm does not find the optimal solution?

If the sets are not individual closed intervals (assume there are not open intervals) I can construct an example by letting one of the sets be two disconnected intervals; but I'm looking for an easier example for a presentation to a non-mathematical audience.

-
It is not clear what you mean by "optimal solution". Indeed, it is not clear what you mean by "solution", since it is not clear what problem your algorithm is trying to solve. And, at the risk of piling on, it is not clear what the "greedy algorithm" is, in this context. Please edit your question so others can know what you have in mind. – Gerry Myerson Feb 22 '12 at 23:27
the set cover problem is a classic NP complete problem, one of the problems off of Karp's list. – Michael Conlen Feb 23 '12 at 2:58
So, Michael, are you interested in getting answers to your question, or aren't you? If you are, meet us halfway, give us something to go on, explain what problem you are trying to solve, what algorithm you are using to solve it, what makes a solution optimal, etc. If you're not interested in getting answers, you're doing just fine, keep up the good work. – Gerry Myerson Feb 23 '12 at 6:17
I think the OP wants to know if the greedy algorithm will fail to obtain the smallest cardinality set of intervals that covers the interval. Here the greedy algorithm is probably the one where you pick the interval that has maximum intersection with the as yet uncovered portion – Suresh Venkat Feb 23 '12 at 8:54
@Suresh, looks like I lied. – Gerry Myerson Feb 23 '12 at 11:28

EDIT: Just to incorporate in the answer what's already in the comments, one simple example consists of the three sets, $[0,1/2]$, $[1/2,1]$, and $[1/5,4/5]$.
@Suresh, starting from zero can fail if there are infinitely many sets. If the sets are $[0,0]$ and $[1/(n+1),1/n]$ for $n=1,2,\dots$, then greedy starting at zero picks $[0,0]$ and spins its wheels forever, unable to make another choice. – Gerry Myerson Feb 23 '12 at 22:23