### Abstract

A closed interval is an ordered pair of real numbers [x, y], with x ≤ y. The interval [x, y] represents the set {i ∈ R{divides}x ≤ i ≤ y}. Given a set of closed intervals 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) = {[x_{1}, y_{1}], [x_{2}, y_{2}], ..., [x_{j}, y_{j}]}, j ≤ k, such that the real numbers represented by I = {n-ary union}_{i = 1}^{k} [a_{i}, b_{i}] equal those represented by M (I) = {n-ary union}_{i = 1}^{j} [x_{i}, y_{i}]. 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 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(log d) parallel time using O(d/log d) processors on an EREW PRAM.

Original language | English |
---|---|

Pages (from-to) | 519-524 |

Number of pages | 6 |

Journal | Information sciences |

Volume | 177 |

Issue number | 2 |

DOIs | |

Publication status | Published - 2007 Jan 15 |

### All Science Journal Classification (ASJC) codes

- Software
- Control and Systems Engineering
- Theoretical Computer Science
- Computer Science Applications
- Information Systems and Management
- Artificial Intelligence

## Fingerprint Dive into the research topics of 'The interval-merging problem'. Together they form a unique fingerprint.

## Cite this

*Information sciences*,

*177*(2), 519-524. https://doi.org/10.1016/j.ins.2006.03.009