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

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.

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.