Overlapping between two intervals: reasoning / algorithm to find the set of disjoint and overlapping intervals

Question

Consider the positive integers {1, 2, 3, 4, ...} and the corresponding Integer Number Line.

Suppose we have four integer numbers, A, B, C and D.

For example:

_________________A___________________________B__________________ ___________________________C__________D_________________________

or

_________________A___________________________B__________________ ___________________________C____________________________D_______

Consider the notation AB as the set of all consecutive numbers A, ...., B, and the interval CD as the set of all consecutive numbers C, ..., D.

I would like to know a simple yet abstract and generalizaed resoning (mathematical demonstration would be really apreciated) that we can apply if we want to find all intervals consisting of the "disjoint" numbers and the "overlapping" numbers between both set of numbers, AB and CD.

Example 1: If AB = {2, 3, 4, 5, 6, 7, 8, 9} and CD = {4, 5, 6, 7}, we have the following subsets for each set AB and CD:

• for AB: {2, 3}, {4, 5, 6, 7} and {8, 9}
• for CD: {4, 5, 6, 7}

Example 2: If AB = {2, 3, 4, 5, 6, 7, 8, 9} and CD = {4, 5, 6, 7, 8, 9, 10, 11, 12}, we have the following subsets for each set AB and CD:

• for AB: {2, 3}, {4, 5, 6, 7, 8, 9}
• for CD: {4, 5, 6, 7, 8, 9} and {10, 11, 12}

But, which one would be a great and yet simple reasoning behind disjoint and overlapping sets of numbers between two given set of integer numbers?

Thanks very much for any clue!!

Answer 1

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<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) &= [A, \max(A,C))\sqcup[\max(A,C),B)\\ &= [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.