# Interval packing problem

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.

• The $k$ to the left of the pictures is to be understood as $\phi(I_j)$ for the red intervals $I_j$ on that level. – Brian M. Scott Jan 18 '12 at 14:22
• Yes, thank you for pointing it out, certainly I created the image a bit misleading. – Listing Jan 18 '12 at 14:24
• I think you mean a different property for (**) than you wrote down. For what you wrote down, we could take $M$ to be all of $(0,7)$ in your example, since the intersection of all the $I_i$ is empty. I think you mean $M\cap\left(\bigcap_{i=1}^k\left(\bigcup\{I_j|\phi(I_j) = i\}\right)\right)=\emptyset$? – joriki Jan 18 '12 at 14:34
• No in the example I allow $(0,7)$ to be taken. It still works in that case (look at the last image, put the bottom interval next to $k=3$ into the green spot and place the $(0,7)$ interval on the bottom level. – Listing Jan 18 '12 at 14:38
• @Listing: Still joriki is right; given $k=1$ (I mean the range of $\phi$, so it must be constant), and $n=2$ with disjoint intervals $I_1=(0,1)$ and $I_2=(1,2)$, the condition is always satisfied because the intersection of all the $I_i$ is empty. Yet clearly one cannot insert $(0,2)$. – Marc van Leeuwen Jan 18 '12 at 15:01

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.

• You beat me to answering this one. But I can resume the idea as follows: repeatedly apply chromosomal crossover to two strands so as to make all free spaces needed for $M$ adjacent, and then place $M$. – Marc van Leeuwen Jan 18 '12 at 15:12
• Oops. For some reason the system didn’t tell me that an answer had already been posted. – Brian M. Scott Jan 18 '12 at 15:20
• @Brian: Yes, that happens to me, too, sometimes. – joriki Jan 18 '12 at 15:22
• @Marc: That’s the way I was thinking of it, in fact. – Brian M. Scott Jan 18 '12 at 15:28
• @Listing: Glad to be of service -- sweet dreams! :-) – joriki Jan 18 '12 at 17:11

The conjecture is true. To avoid endpoint details I’m going to replace your open intervals by left-closed intervals, and instead of $\phi$, I’m going to talk about levels of the picture.

Suppose that $[j,k)$ is the interval to be added that satisfies $(**)$. Write $[j,k)$ as a union of pairwise disjoint intervals, each of which fits into an empty slot on some level; I’ll call them the green intervals. In the example, $[2,4)$ gets split into the green subintervals $[2,3)$ and $[3,4)$. Each level then consists of (possibly) one or more green intervals and some of the old red intervals. Replace the red intervals on each level by the maximal intervals disjoint from the green intervals on that level; call these blue intervals. In the example that would result in blue intervals $[0,2)$ and $[3,7)$ on level $1$, a single blue interval $[0,7)$ on level $2$, and blue intervals $[0,3)$ and $[4,7)$ on level $3$. Each blue interval is a union of original red intervals and possibly some unused spaces, so moving blue intervals intact also preserves the red intervals within them.

Say that the green intervals, from left to right ignoring level, are $G_1,\dots,G_r$. $G_1$ together with the blue interval to its left (if any) exactly matches the blue interval to the left $G_2$, so these intervals can be interchanged to put $G_1$ adjacent to $G_2$ on the same level. (This is not what was done in the example: it would have left level $2$ unchanged, put $[0,3)$ and $[3,5)$ on level $1$, and put the rest on level $3$.) Now replace $G_1$ by $G_1\cup G_2$ and $G_i$ by $G_{i+1}$ for $i=2,\dots,r-1$ and repeat until there is just one green interval.