Minimize the length of intersection of the set of intervals 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.
 A: First of all, the problem can have no solution. Consider intervals $I_n=(0,n)$. No matter how you color them with $k$ colors there will be infinite families with same color
and non-empty intersection. To make the problem meaningful, you must first specify whether
your intervals are open or closed (or else), and second, impose some additional restrictions.
A: 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$.
