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

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.

• This sounds like interval graph coloring, which can be done in linear time if the intervals are sorted. Commented Nov 14, 2019 at 19:59
• @YuvalFilmus that's exactly it, yes. thanks! I'd considered the greedy approach earlier but didn't actually think it was optimal. Commented Nov 14, 2019 at 20:29