Tight instance for unweighted maximum coverage problem? The maximum (unweighted) coverage problem is defined as follows:


Instance: A number $k$ and a collection of sets $S = \{S_1, S_2, \ldots, S_m\}$.
Objective: Find a subset $S^{'} \subseteq S$ of sets, such that $\left| S^{'} \right| \leq k$ and the number of covered elements $\left| \bigcup_{S_i \in S^{'}}{S_i} \right|$ is maximized.


This problem is NP-hard. I am trying to find a counterexample when the greedy algorithm fails but I failed. Especially, can you find a family of instances when the greedy algorithm always fails? (Or at least one simple instance?)


The greedy algorithm:
at each stage, choose a set which contains the largest number of uncovered elements.


I found a family of instances here but it was for the weighted case and I cannot transform it to the unweighted case.
Here is one example:
take the universe   $$U=\{u_1,\dots,u_n,v_1,\dots,v_n\}$$
$S_i=\{u_i,v_i\}$ for $i=1,\dots,n$ , and  $S_{n+1}=\{u_1,\dots,u_n\}$, $m=n+1$, $k=n$