Maximum independent set for intervals by divide and conquer with pruning

Suppose a given set of n intervals contains a maximum independent set of k disjoint intervals. This brief note demonstrates that “divide and conquer with pruning” produces an easy, output‐sensitive O ( n log k )‐time algorithm to compute such a maximum independent set. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 49(2), 158–159 2007