Purpose: Show ways of making operations in Python on sets defined as lists of intervals e.g. sets of the form \(A=[a_1, a_2]\cup[a_3, a_4]\cup\dots\cup[a_{n-1}, a_n]\) and \(B=[b_1, b_2]\cup[b_3, b_4]\cup\dots\cup[b_{m-1}, b_m]\). Done as an exercise, it is likely that there are smarter ways of doing this.
Union of two sets \(A=[a_1, a_2]\) and \(B=[b_1, b_2]\) can be done by first checking that the sets intersect. A check of this can be done using below rule:
\[ \begin{aligned} \left[a_1, a_2\right] \cap \left[b_1, b_2\right] = \emptyset &\iff a_2 \lt b_1 \lor b_2 \lt a_1 \\ &\Updownarrow \\ \left[a_1, a_2\right] \cap \left[b_1, b_2\right] \neq \emptyset &\iff a_2 \geq b_1 \land b_2 \geq a_1 \end{aligned} \]
Using negation and De Morgan's law.
If they intersect then the representation of the union can be reduced from four numbers \(a_1, a_2, b_1, b_2\) to two numbers \(c_1=\min(a_1, b_1)\) and \(c_2=\max(a_2, b_2)\).
\[ \begin{aligned} a_2 \geq b_1 \land b_2 \geq a_1 &\implies \left[a_1, a_2\right] \cup \left[b_1, b_2\right] = \left[c_1, c_2\right] \end{aligned} \]
To reduce unions of intervals \(A=[a_1, a_2]\cup[a_3, a_4]\cup\dots\cup[a_{n-1}, a_n]\) and \(B=[b_1, b_2]\cup[b_3, b_4]\cup\dots\cup[b_{m-1}, b_m]\) one can start by merging the two to
\[ \begin{aligned} C&=[a_1, a_2]\cup[a_3, a_4]\cup\dots\cup[a_{n-1}, a_n]\cup[b_1, b_2]\cup[b_3, b_4]\cup\dots\cup[b_{m-1}, b_m] \\ &=[c_1, c_2]\cup[c_3, c_4]\cup\dots\cup[c_{N-1}, c_{N}] \end{aligned} \] Where \(N=m+n\).
Assume \(C = [c_1, c_2]\cup[c_3, c_4]\cup\dots\cup[c_{N-1}, c_{N}]\) is sorted by the lhs of each interval.
Then
\[ \begin{aligned} (c_2 \geq c_3 \land c_4 \geq c_1) = c_2 \geq c_3 &\implies \left[c_1, c_2\right] \cup \left[c_3, c_4\right] = \left[c_1, \max(c_2, c_4)\right] \\ c_2 \lt c_3 &\implies \left[c_1, c_2\right] \cap \left[c_3, c_4\right] = \emptyset \end{aligned} \]
So if \(c_2 \geq c_3\) then merge the two intervals and if \(c_2 \lt c_3\) then start a new disjoint interval \(\left[c_3, c_4\right]\) and repeat.
from collections import defaultdict
from typing import List
ListOfIntervals = list[list[float]]
def reduce(C: ListOfIntervals) -> ListOfIntervals:
"""Reduces a list of intervals to a compressed form.
Returns:
ListOfIntervals: A compressed list of intervals without overlapping intervals
and sorted by the lhs of each interval.
"""
C_sorted = sorted(C, key=lambda x: x[0]) # Sort by lhs
union = [list(C_sorted[0])] # Initialize with a copy
for lhs, rhs in C_sorted[1:]:
if union[-1][1] >= lhs: # c_2 >= c_3
if rhs >= union[-1][1]: # max(c_1, c_4)
union[-1][1] = rhs
else:
union.append([lhs, rhs]) # If they don't intersect then start new
return unionA = [[2, 5], [1, 3]]
B = [[8, 10]]
print(reduce(A))
print(reduce(B))
print(reduce(A + B)) # union[[1, 5]]
[[8, 10]]
[[1, 5], [8, 10]]
A = [[1, 3], [3, 5]]
B = [[8, 10]]
print(reduce(A))
print(reduce(B))
print(reduce(A + B)) # union[[1, 5]]
[[8, 10]]
[[1, 5], [8, 10]]
A = [[1, 6], [7, 8], [9, 10], [10, 10], [11, 12], [11, 12]]
B = [[2, 4], [4, 8], [9, 11], [10, 10], [14, 16]]
print(reduce(A))
print(reduce(B))
print(reduce(A + B)) # union[[1, 6], [7, 8], [9, 10], [11, 12]]
[[2, 8], [9, 11], [14, 16]]
[[1, 8], [9, 12], [14, 16]]
Feel free to comment here below. A Github account is required.