I've been trying to find an efficient way to solve the problem of finding a minimum (not minimal) set of time points that cover a given family of intervals on the real line, that is, for each interval $I$ there should be some time point $t$ from the chosen set such that $t \in I$. However, I am not sure if it's that straightforward. I tried modeling it as a minimum edge cover problem ("P" polynomial time complexity: intervals are vertices and intersection between intervals is an edge), but that doesn't work because for 1 time point in optimum solution there can be multiple edges.
I developed a greedy solution: have intervals sorted in increasing order of their end times. Then iterate over the intervals in the order. If a time point hasn't been inserted into the solution that covers the current interval, then insert it and remove all intervals that are covered by it from consideration. Continue till no intervals remaining. Example: (0, 10), (3, 12), (11, 15)
Add time 10 to the solution. Remove (0, 10) and (3, 12) from consideration. Add time 15 to solution. Remove (11, 15) from consideration. Final solution is of size 2. (time 10 and 15).
I can't prove it's optimum because it's not modeled as edge cover or vertex cover or known graph problem. I tried modeling it as "minimum clique cover problem" but not sure if it works.
- How to model it properly to understand its complexity (P vs NP complexity)?
- How to know if the above solution is optimum?