This was from a test from my university:
Consider $T = t_1, t_2, \cdots, t_n$ a set of intervals of the form $(s, e)$, representing the start and end time, respectively. Now, select the minimum number of intervals such that their "union" intersects all other intervals. The question then asked for an optimal greedy algorithm.
From what I can see, this is a vertex cover problem (each interval is a vertex; draw an edge between each pair of intervals that intersect), which is NP-complete on general graphs.
Consider $W(i)$ the number of intervals intersecting $i$, and $M$ a set of intervals already covered. Here is my solution:
- Order $T$ by $W$ and insert in $T_{ord}$;
- If $T_{ord} = \emptyset$ terminate
- Remove the first element $e$ from $T_{ord}$;
- If $e \in M$ go to $2$;
- Decrease $1$ for every element $e^{'}$that intersect $e$, and $M \cup\{e,e^{'}\}$;
- Order $T_{ord}$ and go to $2$.
I managed come up with a greedy solution, but couldn't come up with a counterexample. Given that, I was thinking if this is a special case of the vertex cover problem. Is it?