I am reading the book "Approximation Algorithm" by Vijay V Vazirani http://athena.nitc.ac.in/~kmurali/Courses/CombAlg2014/vazirani.pdf
And in proof of Lemma 2.3, the author said "In the iteration in which $e_k$ was covered, $\overline{C}$ contained at least $n-k+1$ elements." without any claims.
But this is not so trivial for me. Can anyone give me some hint or explain?
This is based on the fact that you update the sets in the following in each iteration in the following manner: Let $\hat{S}_i$ be the set with the minimum cost-effectiveness. Then update for all sets which indices are not yet added to the solution index set $\hat{S}_{j}= \hat{S}_{j} - \hat{S}_{i}$ $\forall j \neq i$. Therefore no set will contain the elements which are already added and hence in each iteration at least one new element is covered by the solution. Then you have trivially $\frac{1}{n-k+1}$ elements left at the start of the $k$-th iteration.