# On the k-coloring of Intervals

### Martin C. Carlisle and Errol Lloyd

May 1991

**Abstract**
The problem of coloring a set of intervals (from the real line) with a set
of k colors is studied. In such a coloring, two intervals may have the
same color if and only if those intervals do not overlap. Two versions of
the problem are considered. For the first, we provide an O(k+n) time
algorithm for k-coloring a maximum cardinality subset of the intervals.
The best previous algorithm for this problem required time O(kn). In the
second version, we assume that each interval has a weight, and provide an
O(knlogn) algorithm for k-coloring a set of intervals of maximum total
weight. The best previous algorithm for this problem required time O(n^2logn).
These results provide improved solutions to problems of local register
allocation, task scheduling, and the routing of nets on a chip.

This paper appeared in the Proceedings of the International Conference on
Computing and Information, Ottawa, Canada. Also as Springer-Verlag LNCS 497
(pages 90-101), and in journal form in Discrete Applied Mathematics
59(1995) pp. 225-235.