R. Sridhar and N. Chandrasekharan, "Highly parallelizable
problems on sorted intervals", <I>Parallel Computing</I>, 1995, Vol.
21, pp. 433-446. 
<P>

In this paper, it is shown that the problem of finding the shortest
interval path (see, e.g., a review of Atallah et al. 1995) is {\it
highly parallelizable} in the sense that it can be solved in time
$O(\log\log(n))$ on $O(n/\log\log(n))$ processors with the possibility
of Concurrent Read and Concurrent Write (CRCW
PRAM). Similarly to an algorithm from Atallah et al. 1995, this
parallel algorithm requires that the endpoints of the intervals have
already been sorted. <P>

Several other interval-related problems are also proven to be highly
parallelizable, including a similar problem of finding the largest set
of pairwise non-intersecting intervals. This problem occurs, e.g.,
when we schedule $n$ tasks with time intervals $[t^-_i,t^+_i]$ and
values $c_i$; under the condition that at any moment of time, only one
task can be performed, we want to maximize the total value generated
by the tasks.