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={[a1,b1],[a2,b2],…,[ak,bk]}, the Interval-Merging Problem   is to find a minimum-cardinality set of intervals M(I)={[x1,y1],[x2,y2],…,[xj,yj]}M(I)={[x1,y1],[x2,y2],…,[xj,yj]}, j ⩽ k  , such that the real numbers represented by I=⋃i=1k[ai,bi] equal those represented by M(I)=⋃i=1j[xi,yi]. In this paper, we show the problem can be solved in O(d log d) sequential time, and in O(log d) parallel time using O(d) processors on an EREW PRAM, where d   is the number of the endpoints of II. 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(log d) parallel time using O(d/log d) processors on an EREW PRAM.