Overlapping between two intervals: reasoning / algorithm to find the set of disjoint and overlapping intervals
For two integers $A$ and $B$ where $A\le B$, let $[A,B)$ denote the half-closed half-open interval that consists of the numbers $A, A+1, \cdots, B-1$. In particular, if $A&lt;B$, then there are $B-A$ numbers in $[A,B)$. If $A=B$, then there is no numbers in $[A,B)$. For example, 


$[0,1)$ means the number 0. 
Both $[0,0)$ and $[3, 3)$ mean no numbers.
$[5,11)$ means the numbers $5,6,7,8,9,10.$
To denote the numbers $-2, -1, 0, 1, 2$, we can use $[-2, 3)$.




A nice property of half-closed half-open interval: If $L\le M \le R$, then $[L,R) = [L,M) \sqcup [M,R)$.

Proof: I am afraid it is obvious by definition. Done.



Suppose we are given $[A, B)$ and $[C, D)$, where $A\lt B$ and $C\lt D$. Then $[A,B)$ overlaps $[C,D)$ if and only $\max(A,C)\lt \min(B,D)$. 

Proof: 

"$\Rightarrow$": Let $n$ be a number in both $[A,B)$ and $[C,D)$, i.e.,
$A\le n\lt B$ and $C\le n \lt D$. Then $\max(A,C)\le n\lt \min(B,D)$.

"$\Leftarrow$": $A\le \max(A,C)\lt \min(B,D)\le B$, i.e., $\max(A,C)\in [A,B)$. Similarly, $\max(A,C)\in [C,D)$. So $[A,B)$ overlaps $[C,D)$.

Done.



Suppose $[A,C)$ and $[B,D)$ overlap. Then we have the following set decompositions.


$[A,B) = [A, \max(A,C))\sqcup[\max(A,C), \min(B,D)]\sqcup[\min(B,D), B)$
$[C,D) = [C, \max(A,C))\sqcup[\max(A,C), \min(B,D)]\sqcup[\min(B,D), D)$


Proof:

We have $A\le \max(A,C) \le \min(B,D)\le B$. So,

$$\begin{align}
[A,B) &amp;= [A, \max(A,C))\sqcup[\max(A,C),B)\\
&amp;= [A, \max(A,C))\sqcup[\max(A,C), \min(B,D)]\sqcup[\min(B,D), B).
\end{align}$$



Example 1: If $I = \{2, 3, 4, 5, 6, 7, 8, 9\}$ and $J = \{4, 5, 6, 7\}$, then $I=[2,10)$ and $J=[4,8)$. We have the following set decompositions.


$[2,10) = [2, 4)\sqcup [4, 8) \sqcup [8,10)$.
$[4,8) = [4, 4)\sqcup [4, 8) \sqcup [8,8) = [4,8)$.


Example 2: If $I = {2, 3, 4, 5, 6, 7, 8, 9}$ and $J = {4, 5, 6, 7, 8, 9, 10, 11, 12}$, then $I=[2,10)$ and $J=[4,13)$. We have the following set decompositions. 


$[2,10) = [2, 4)\sqcup [4, 10) \sqcup [10,10)= [2, 4)\sqcup [4, 10)$.
$[4,13) = [4, 4)\sqcup [4, 10) \sqcup [10,13)= [4, 10) \sqcup [10,13)$.




The above examples should indicate clearly enough the algorithm that decomposes two overlapping intervals into disjoint intervals.