Now suppose there are $k$ sets in the optimal solution and let that be $OPT = \{O_1,...,O_k\}$
Here the sets in the family look like intervals of integers because they contain only consecutive numbers.
Let $I_1,...,I_n$ be the given sets where $I_i = \{j+1,...,j+k\}$. We define the left and right endpoints of any such interval as $L(I_i) = j+1$ and $R(I_i) = j+k$ and $|I_i| = k$
Now let us fix one set from the optimal solution and without loss of generality, let's call it $O_1$. We will show that $O_1$ can intersect at most some constant number of sets $I_j$s that we output from the greedy solution.
No set from the greedy solution can be a subset of $O_1$, because $O_1$ is a set in the family, and in that case, the greedy algorithm will pick $O_1$ and not its subset in the first place.
Among the sets that are intersecting $O_1$, one cannot be subset of another, i.e if $I_1,I_2$ intersect $O_1$ at some points, then neither $I_1 \subset I_2$, nor $I_2 \subset I_1$. This is because the greedy solution will have picked up the bigger set in the first place.
The above two observations show that when some $I_i$ intersect $O_1$, $I_i-O_1 \neq \phi$. Now we consider two situations of some sets $I_1, I_2$ intersecting $O_1$.
Suppose we have $I_1,I_2$ intersecting $O_1$, such that $L(I_1) < L(O_1) < L(I_2) < R(I_1) < R(O_1) < R(I_2)$.
This is the case where $I_1, I_2$ intersect each other. Depending on the sizes, both are taken up by the greedy algorithm. Now suppose $O_1$ intersects with another set $I_3$, we will try to figure out how this $I_3$ will look like and what its range can be.
$I_3$ can intersect only $I_2$, or can intersect only $I_1$ or can intersect both $I_1,I_2$. Let us first consider the case when $I_1$ intersects $I_2$, the case where $I_3$ intersects $I_1$ will be exactly similar.
So we know, we must have $L(I_3) > L(I_2)$ and $R(I_3) > R(I_2)$. Observe that $I_3$ must be maximal of these types of sets, because if we have another $I_4$ continuing this sequence with $L(I_4) > L(I_4)$ and $R(I_4) > R(I_4)$, then this contradicts the greedy algorithm. After we take up $I_2$ by the algorithm, $I_4$ covers more elements than $I_3$, so $I_3$ will not be taken up in the first place. So there can only be one set of that type, call it $I_3$.
The argument when $I_3$ intersects $I_1$ and not $I_2$ is exactly similar. This means we can have two more sets in each direction, we can call these $I_3, I_4$ that intersect $O_1$ too. Now consider the set $I_5$ where we have $L(I_1) < L(I_5) < L(O_1)$ and $R(O_1) > R(I_5) > R(I_2)$. Again we can repeat the same argument and say that $I_5$ is the maximal in this type of set, we cannot have a sequence of such sets because after $I_2, I_1$, we will choose the maximal of these sets in the first place. But given that the greedy algorithm has already chosen $I_3, I_4$, it will not choose $I_5$ anymore. If we have $L(I_2) < L(I_5) < R(I_1)$ and $R(I_5) > R(I_2)$, then the greedy algorithm will never pick $I_2$. So $O_1$ can intersect at most 4 sets in this case.
This is the case where $I_1,I_2$ do not intersect each other. In this case, as before we will have $I_3, I_4$ as usual in either direction, say $I_3$ in direction of $I_1$ and $I_4$ in direction of $I_2$. But in this case, we might not have any other set to cover between $R(I_1)$ and $L(I_2)$, apart from $O_1$ which is itself in the family of sets. If there is a set larger than $O_1$ satisfying the above analysis, the greedy algorithm will be taking that set to cover this part, else it will take $O_1$ itself to cover this part. It might also be the case that $L(O_1) < R(I_3) < L(I_5) < R(I_1) < L(I_2) < L(I_4) < R(I_5) < R(I_4)$, or it might be the case in the exact opposite direction, but any one of these sets will need to be chosen to cover the remaining part.
So $O_1$ will be intersecting 5 sets from the greedy algorithm in this case.
The number of sets selected by the greedy algorithm is upper bounded by five times the number of
sets in the optimal solution.
In the whole analysis above, we chose one set from the optimal solution called $O_1$, it was an arbitrary set, so the whole analysis is true for any $O_i \in OPT$. Here we have $|OPT| = k$.
We see that each $O_i$ intersects at most 5 sets from the greedy solution, so if we output the sets from the greedy solution, we are overcounting the optimal solution by at most five times. So the number of sets in the greedy solution is at most $5k$
We must have $L(O_1) < L(O_2) < ... < L(O_k)$, given that the sets are ordered from left to right by the portions of the number line they cover. This is because if $L(O_i) = L(O_{i+1})$, then one of the sets will be a subset of another and so no more be an optimal set.
Pick any element from $1, ..., n$, say $i$, then it can belong to at most two of the optimal sets. If we have $i$ inside $O_i, O_{i+1}, O_{i+2}$, then this means that we don't need $O_{i+1}$ in the set cover, and the collection is no more optimal.
The best approximation factor $c$ can not be less than 2
We have $U = \{1,...,n\}$ and consider the given family of sets $F = \{[1,k], [k+1,2k],..., [n-k+1,n]\} \bigcup \{[1,k+1],[k+3,2k+3],[2k+5,3k+5],...\}$. This means the family contains $n/k$ intervals of size k which completely cover $U$. But the family also contains approximately $\frac{n}{k+1}$ intervals of size $k+1$ spaced apart by 1. Our standard greedy algorithm selects the latter subset of intervals since each one spans $k+1$ uncovered elements. But at the end it will be forced to add approximately $\frac{n}{k+2}$ more intervals to cover the numbers $k+2,2k+4,...$ and so on. So it ends up selecting twice the number of sets of the optimal.
Now I will try to reduce the approximation factor but I am not sure if this is right.
Consider a particular set $O$ from the optimal solution. Among all the sets from the greedy solution that intersect this set, consider only those whose leftmost endpoint lies in this set $O$. Then there can be at most two such sets.
Consider the optimal solution and lets order the sets in that solution as $O_1,...,O_k$. Now fix one such set $O_i$. Suppose there is an interval $I_1$ from the greedy solution, such that we have $L(I_1)> L(O_i)$ and then we must have $R(I_1) > R(O_i)$ because otherwise the interval will become a subset of $O_i$ and the greedy solution will pick the optimal set instead of $I_1$. So we charge $O_i$ once for this $I_1$.
Now note that we can have a sequence of such sets satisfying the exact conditions like $I_1$. Let us look at two such sets $I_2,I_3$, where we have $L(O_i)< L(I_3) <L(I_2)<L(I_1)$ and also $R(O_i)<R(I_3) <R(I_2)<R(I_1)$, to prevent one interval to be subset of another.
But now observe that this cannot hold. Once $I_1$ has been picked by the greedy algorithm, it will directly pick $I_3$ and not $I_2$ because it covers more elements. So there cannot be a sequence of such sets with their left endpoints inside $O_i$, we can have at most two of them.
The only way that we can have another set $I_4$ intersecting the $O_i$ to the left of $I_3$, apart from the sequence, will be to have $R(I_4) < L(I_3)$, in which case $L(I_4)$ is inside $O_{i-1}$.
In the previous approach, we were charging each optimal set the number of times it has intersected any set from the greedy solution so that a maximal number of times any optimal set has been charged is the approximation factor. In this approach, we will only charge an optimal set by the number of times it intersects only the kind of sets whose left endpoint lies within it. Thus by the above lemma, we can charge at most twice. So this should give an approximation factor of 2.
