M. A. Bender, M. Gastaldo, and M. Morvan, "Parallel interval order recognition and construction of interval representations", Theoretical Computer Science, 1995, Vol. 143, pp. 73-91.

The authors propose parallel algorithms for solving the following scheduling problem: we have $n$ tasks $t_1,...,t_n$, and we have selected $m$ pairs $(t_{f(i)},t_{s(i)})$ of these tasks ($1\le i\le m$) that must overlap in time. We must schedule these $m$ tasks (i.e., map each of them into a time interval) in such a way that only intervals that correspond to $m$ given pairs of tasks overlap, and intervals corresponding to other pairs don't overlap. The proposed algorithms run in time $O(\log(n))$ on $n+m$ processors and in constant time on $O(n^2)$ processors.