Algorithm to return largest subset of non-intersecting intervals

I need an efficient algorithm that takes input a collection of intervals and outputs the largest subset of non-intersecting intervals.

i.e. Given a set of intervals $I = \{I_1, I_2, \ldots, I_n\}$ of the real line, we need to output a set of intervals $O = \{O_1, O_2, \ldots, O_k\}$ such that

• $O$ is a subset of $I$.

• For any $i \neq j$, $O_i$ and $O_j$ are non-intersecting.

• $k$ is the maximum possible.

Example: if the intervals are $[1,100], [2,3], [4,5], [6,7], [3,20]$ we should return $\{[2,3], [4,5], [6,7]\}$.

There is an $O(n \log n)$ time algorithm (which in some models is optimal, because of the bounds for the element distinctness problem).

We first sort the intervals by their right end point. Suppose the sorted order is
$I_1, I_2, \ldots, I_n$.

Now for each interval, we try to compute the size of the largest possible non-intersecting set, with that interval being the rightmost interval in that set. We pick the interval which gives the maximum (as any non-intersecting set has a rightmost interval).

This we do using dynamic programming.

Suppose we have computed the sizes (say $S_1, \ldots, S_n$) for intervals up to $k-1$.
Now you want to compute for $I_k = [L_k, R_k]$.

Pick $L_k$, and do a binary search in $[R_1,R_2, \ldots, R_k]$. Say $R_j \lt L_k \lt R_{j+1}$.

Now all the intervals $1,2,\ldots,j$ do not intersect $I_k$ (and all others up to $I_{k-1} \cap I_k$). Thus we need to pick the max among $S_1, S_2, \ldots, S_j$ and add $1$ to it. This maximum can also be computed dynamically, in a separate array, along with the $S$.

This can be implemented so that the whole algorithm runs in $O(n \log n)$.

We can also modify this algorithm a little to give you the actual intervals which form the non-intersecting set.

StackExchange Computer Science Q#10713, answer score: 8