Computing minimum partition of poset of $N$ intervals into chains in $o(N^{2.5})$ time?
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.