3
$\begingroup$

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.

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.