Suppose there are intervals in the format of r = (start, end), and D = {r1, r2, ..., rn).
Now we would like to partition D into several partitions (let's say m) where each partition has roughly similar size (n/m), and the overlap between partitions is minimum.
The overlap between partition $p_i$ and $p_j$ is defined as $f(p_i, p_j) = \max\{0, \min\{p_i.end, p_j.end\} - \max\{p_i.start, p_j.start\}$
where $p_i.start$ and $p_i.end$ are the leftmost and rightmost endpoints in $p_i$. Similar definition for $p_j$.
Is there any solution?
If there is no any two intervals overlapping each other, I have a heuristic method: sort these intervals, and split them (every n/m is a partition). But I do not know the correctness of this method.