The interval-merging problem
A closed interval is an ordered pair of real numbers [x,y], with x?y. The interval [x,y] represents the set {i?R?x?i?y }. Given a set of closed intervals I={[a1,b1],[a2,b2],,[ak,bk]} I = { [ a 1 , b 1 ] , [ a 2 , b 2 ] ,  , [ a k , b k ] } , the Interval-Merging Problem  is to find a minimum-cardinality set of intervals M(I)={[x1,y1],[x2,y2],,[xj,yj]} M ( I ) = { [ x 1 , y 1 ] , [ x 2 , y 2 ] ,  , [ x j , y j ] } , j?k , such that the real numbers represented by I = ? i = 1 k [ a i , b i ] equal those represented by M ( I ) = ? i = 1 j [ x i , y i ] . In this paper, we show the problem can be solved in O(dlogd) sequential time, and in O(logd) parallel time using O(d) processors on an EREW PRAM, where d  is the number of the endpoints of I I . Moreover, if the input is given as a set of sorted endpoints, then the problem can be solved in O(d) sequential time, and in O(logd) parallel time using O(d/logd) processors on an EREW PRAM.
interval-merging pram design and analysis of algorithms parallel algorithms data structures