Computing minimum partition of poset of $N$ intervals into chains in $o(N^{2.5})$ time?

Question

Consider a set $P$ of $N$ intervals $\{I_i = (l_i, r_i)\}$ partially ordered according the standard interval order: $I_i < I_j$ iff $r_i \le l_j$.

I want to find a minimum cardinality partition of $P$ into chains. By Dilworth's theorem, the cardinality will equal the maximum cardinality of any antichain. We can find such a maximum antichain in $O(N\log N)$ time: note that $I_i$ and $I_j$ are incomparable iff $I_i\cap I_j \ne \emptyset$, and applying Helly's theorem in one dimension, deduce that any antichain has nonempty overall intersection, and hence any maximal antichain $A$ is exactly the set of intervals containing $x$ (let us call this $A(x)$) for some point $x$. So it is sufficient to find a point $x$ that maximizes $|A(x)|$. After sorting the endpoints this can be done in $O(N)$ time.

I'm having trouble getting the dual partition though. We can find an optimal partition in $O(N^{2.5})$ time using Hopcroft-Karp to compute a maximum bipartite matching, but it seems like it should be possible to get close to linear time in this case using the duality between antichains and chain partitions. Unfortunately staring at the Wikipedia pages for Dilworth's and Kőnig's theorems doesn't seem to be getting me anywhere.

Answer 1

Your problem is the same as interval graph coloring.

There is a well-known greedy algorithm solving the problem optimally, running in linear time if the intervals are already sorted.