= Interval stabbing problem
Given finitely many nonempty <closed intervals> $[s_i,e_i]$, choose as few points as possible so that each interval contains a chosen point. An optimal <greedy algorithm> repeatedly chooses the smallest end of an uncovered interval. After choosing $t$, any still uncovered interval starts strictly after $t$, since its end cannot be smaller than $t$. Thus the intervals whose ends trigger successive choices are pairwise disjoint. Every feasible point set needs a separate point in each triggering interval, proving that the greedy point set is optimal. Sorting by end and scanning takes $O(n\log n)$ time. The inclusion of endpoints means an interval starting at the last chosen point is already covered.
Back to article page
