Consider the following problem: given a finite set $S$ of intervals on the line and a number $k$. We need to colour this set in $k$ colours so that the measure of the set of points, which are contained in two or more intervals coloured with the same colour, is minimal for given $k$. By colouring a set $S$ in $k$ colours I mean a map from $S$ to $\{1, 2,\ldots, k\}$.


I wonder, if there are any papers on this problem or related problems.



Minimize the length of intersection of the set of intervals
Let $I\_1,\ldots,I\_n$ be the intervals in $S$. For simplicity, we may assume that the intervals are open and that all $2n$ endpoints are distinct. The latter property can be ensured by changing the intervals slightly, which changes the value of the objective function by an arbitrarily small amount. Furthermore, we may assume that $k\geq 2$.


Let $x\_1<x\_2<\ldots<x\_{2n}$ be the $2n$ endpoints of the intervals $I\_1,\ldots,I\_n$.
For $i\in \{ 1,\ldots,2n-1\}$, let $J\_i=(x\_i,x\_{i+1})$.
By construction, all points in $J\_i$ are contained in the same number $\omega\_i$ of intervals in $S$.
The interval $J\_i$ is {\it bad} if $\omega\_i>k$.
Clearly, for every coloring $c:S\to \{ 1,2,\ldots,k\}$, 
the set of points that are contained in two or more intervals coloured with the same colour, contains every bad interval,
that is, the total measure of the bad intervals is an obvious lower bound.
Let $B$ be the union of all bad intervals.


We claim the existence of a coloring $c$
such that the set of points that are contained in two or more intervals coloured with the same colour, is exactly $B$, that is, the above lower bound actually gives the optimum value.
We prove this claim by induction on the number of bad intervals.


Note that $\max\{ \omega\_i:i\in \{ 1,\ldots,2n-1\}\}$ is the clique number $\omega(G)$ of the interval graph $G$ defined by the intervals in $S$.
Therefore, if there are no bad intervals and $B$ is empty, then the perfection of interval graphs implies $\chi(G)\leq k$, which implies the existence of a coloring $c$ such that no point is contained in two or more intervals coloured with the same colour.


Now, let $B\not=\emptyset$.
Let $J\_i$ be the leftmost bad interval.
Let $x=x\_i$ be the left endpoint of $J\_i$.
Note that, since $k\geq 2$, we have $i\geq 2$.
Clearly, $x$ is the left endpoint of some interval $I\_r$ in $S$.
Let $R\subseteq S$ be such that $R$ contains $I\_r$ as well as every interval in $S$ that contains $x$.
Let $y$ be the leftmost right endpoint of any interval in $R$.
Note that $B\setminus (x,y)$ is a finite set, that is, a set of $0$ measure.
Let $y$ be the right endpoint of the interval $I\_s\in R$.
If $r\not=s$, then let $S'$ arise from $S$ by replacing the two intervals $I\_r$ and $I\_s$ by their union $I'=I\_r\cup I\_s$.
If $r=s$, then $R$ contains an interval $I\_s$ that is distinct from $I\_r$ such that $[x,y]\subset I\_s$. Again,
let $S'$ arise from $S$ by replacing the two intervals $I\_r$ and $I\_s$ by their union $I'=I\_r\cup I\_s$.
By construction, the collection $S'$ of intervals leads to fewer bad intervals. Let $B'$ denote the union of the bad intervals associated with $S'$. Clearly, $B$ differs from $B'\cup (x,y)$ by a finite set.
By induction, there is a coloring $c'$ of $S'$ with $k$ colors
such that the set of points that are contained in two or more intervals in $S'$ coloured with the same colour by $c'$, is exactly $B'$.
Let $c$ be the coloring of $S$ such that $c\mid\_{S\setminus \{ I\_r,I\_s\}}=c'\mid\_{S'\setminus \{ I'\}}$ and $c(I\_r)=c(I\_s)=c'(I')$.
By construction, 
the set of points that are contained in two or more intervals in $S$
coloured with the same colour by $c$, is exactly $B$.


