Yesterday I came up with this problem and I just cannot get it out of my head:
Problem: Consider a finite $I$ set of integer-valued intervals $I_i=(a_i,b_i)$ $i = 1,\ldots,n; a_i \in \mathbb{N_0}, k \in \mathbb{N}, I=( I_1,\ldots,I_n\ )$
Assume there is a map $\phi: I \longrightarrow \{1,\ldots,k\}$ such that
$$(*): \{l, m\} \subset \{1,\ldots,n\}, l \neq m, \phi(I_l)=\phi(I_m) \Rightarrow I_l \cap I_m=\emptyset$$
Now if $M=(x,y)$ is an inteval such that $(**): M\cap\left(\bigcap_{i=1}^k\left(\bigcup\{I_j|\phi(I_j) = i\}\right)\right)=\emptyset$. then $M$ can be always appended to $I$ with a new map $\phi'$ such that property $(*)$ holds.
Example: $k=3$, $I=( (0,2), (3,5), (2,4), (5,7), (0,3), (4,6) )$, $\phi(I)=( 1,1,2,2,3,3)$
This corresponds to the following image (edit: the $k$ on the left side is a bit misleading, better ignore it):
As you can see the property $(*)$ is fullfilled (no intervals are overlapping in their time line). We can also see that for the interval $(2,4)$ he have the property $(**)$ i.e. we find spaces to put it into the image:
Now the theorem tells us that there is a new image where the green interval does not have to be broken. And indeed we find $\phi(I \cup (2,4))=(1,2,3,2,2,2,1,1)$.
Or in the image:
I hope I could explain the problem well. I am not sure if the theorem is correct but I tried quite a few examples and it always worked out.
Best Answer
Assuming that instead of $(**)$ you meant $M\cap\left(\bigcap_{i=1}^k\left(\bigcup\{I_j|\phi(I_j) = i\}\right)\right)=\emptyset$, then yes, this will always work.
Without loss of generality, we can assume that the only spaces left in the rows are exactly the ones required for $M$; if not, we can fill any remaining empty spaces without making the problem easier.
Now within a row there may be transitions from empty space to filled space and/or from filled space to empty space. Since there is at most one empty space per column and the empty spaces are all consecutive ($M$ being an interval), these two types of transitions are paired up, except for an unpaired initial transition from filled space to empty space and an unpaired final transition from empty space to filled space (where the margins count as filled space in case $M$ touches them).
Now in each row except for the one containing the unpaired initial transition, go through from the front and when you hit a transition from filled space to empty space switch to the row containing the corresponding transition from empty space to filled space. In this manner you can fill an entire row with filled space. What's left after this is the filled space before the unpaired initial transition and the filled space after the unpaired final transition. Put these together in the remaining row, and $M$ fits snugly between them.