Upper bound for amount of intervals in intersection of interval sets

Question

I have two sets of numbers which are unions of disjoint intervals, and I have to find an upper bound for how many of such intervals can there be in the intersection of the two sets. Here's a diagram of how that would look like. After trying for a couple of examples it seems to me that this upper bound is |A| + |B| - 1, where |A| would be the amount of intervals in set A. However, I'm not sure this is the best upper bound, and I'm also not sure of how one would go about proving it

Answer 1

Let the two families of intervals be $\mathscr{A}$ and $\mathscr{B}$. Let

$$\mathscr{A}_0=\left\{A\in\mathscr{A}:A\cap\bigcup\mathscr{B}=\varnothing\right\}$$

and

$$\mathscr{B}_0=\left\{B\in\mathscr{B}:B\cap\bigcup\mathscr{A}=\varnothing\right\}\;.$$

For each $A\in\mathscr{A}\setminus\mathscr{A}_0$ let

$$\mathscr{B}_A=\{B\in\mathscr{B}:A\cap B\ne\varnothing\}\;,$$

and let

$$\mathscr{I}_A=\{A\cap B:B\in\mathscr{B}_A\}\;.$$

It’s not hard to see that $|\mathscr{I}_A|=|\mathscr{B}_A|$. It’s also clear that if $A_0,A_1\in\mathscr{A}$, $B_0\in\mathscr{B}_{A_0}$, and $B_1\in\mathscr{B}_{A_1}$, then $A_0\cap B_0\ne A_1\cap B_1$, so $\mathscr{I}_{A_0}\cap\mathscr{I}_{A_1}=\varnothing$, and it follows that the total number of intervals is

$$|\mathscr{A}_0|+|\mathscr{B}_0|+\sum_{A\in\mathscr{A}\setminus\mathscr{A}_0}|\mathscr{I_A}|=|\mathscr{A}_0|+|\mathscr{B}_0|+\sum_{A\in\mathscr{A}\setminus\mathscr{A}_0}|\mathscr{B}_A|\;.\tag{1}$$

Next, note that no member of $\mathscr{B}$ belongs to more than two of the sets $\mathscr{B}_A$ for $A\in\mathscr{A}$, and this happens only when $B\in\mathscr{B}_{A_0}\cap\mathscr{B}_{A_1}$ for adjacent intervals $A_0,A_1\in\mathscr{A}$. Thus, at most $|\mathscr{A}|-1$ members of $\mathscr{B}$ can be counted twice in the last term of $(1)$, all are counted at least once, and none can be counted more than twice. It follows that

$$\begin{align*} |\mathscr{A}_0|+|\mathscr{B}_0|+\sum_{A\in\mathscr{A}\setminus\mathscr{A}_0}|\mathscr{B}_A|&\le|\mathscr{A}_0|+|\mathscr{B}|+|\mathscr{A}\setminus\mathscr{A}_0|-1\\ &=|\mathscr{A}|+|\mathscr{B}|-1\;. \end{align*}$$

It’s easy to show that this upper bound can be attained.