Given a set of intervals (pairs of real numbers), we look at the problem of finding a minimal partition of this set such that no element of the partition contains two overlapping intervals. We exhibit a Θ(N log N) algorithm which is optimal. The problem has applications in LSI layout design and job scheduling.
No takes yet. Share an insight, caveat, or question.
Gupta et al. (1979) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: