Given a set of intervals on the real line, find a minimum set of points that "cover" all the intervals
The problem is in $\mathbf{P}$.

In fact, there is even a (very) efficient algorithm for it:

Let $[a_1, b_1], \dots, [a_n, b_n]$ be the input intervals and assume $a_i \le b_i$ for all $i$. Additionally, let us assume (for now) that the intervals are given in sorted order as a list, sorted firstly respective to the $a_i$ and secondly to the $b_i$.

An optimal solution can be found as follows: Set $r$ to $a_1$. Then, starting with $i = 1$, check if $a_{i+1} \le b_i$; if that is the case, set $r$ to $a_{i+1}$ and increment $i$; otherwise, add $r$ to the solution and eliminate all intervals from $[a_1, b_1]$ up to $[a_i, b_i]$. Repeat until no more intervals are left.

Why is this an optimal solution? $[a_1, b_1]$ must be covered, so there must be some $r \in [a_1, b_1]$ in the solution. Then, either $r$ covers all $n$ intervals or there is $i$ such that $r &lt; a_{i+1}$. The way our solution is constructed, $r$ is chosen so as to cover a maximal number of intervals while preserving these two conditions for $r$ (i.e., $a_1 \le r \le b_1$ and $r &lt; a_{i+1}$). Apply induction on the remaining intervals (i.e., $[a_j, b_j]$ with $j \ge i + 1$).

The above procedure runs in linear time in $n$. The bulk of the time complexity, thus, lies in sorting the intervals, which can be done in $O(n \log n)$. I do not believe there is a better solution than this (though how to prove it does not occur to me at the moment).



A note

After some thought, the solution you have given also seems to be optimal (in fact, the only significant difference is you pick end times instead of start times). Proving it is optimal is analogous to the argument above: Set $r$ to $b_1$; if $a_2 \le b_1$, then $r$ already covers $[a_2, b_2]$, so disconsider it; otherwise, $a_2 &gt; b_1$ and there is no $r$ covering both $[a_1, b_1]$ and $[a_2, b_2]$. Apply induction.

The time complexity is still $O(n \log n)$, though, since you require sorting the end times first.