Découpage d'intervalles en Python

On arrive au genre d'exercice où la résolution simple de la première partie devient inapplicable à la seconde partie, parce qu'il lui faudrait plus de mémoire qu'il n'y en a sur Terre ou plus de temps que l'âge de l'univers. Là, on est plutôt dans le second cas, je dirais.

Bref, ce n'est pas la première fois que je me retrouve à couper des intervalles en morceaux, alors c'est cadeau, voici du code pour faire ça. Je réutilise le type range qui correspond plutôt bien au concept.

def intersects(range1: range, range2: range) -> bool:
 """Tell whether or not the two ranges have a part in common."""
 if range1.start >= range1.stop or range2.start >= range2.stop:
 raise ValueError("usupported empty range") 
 if range1.step != 1 or range2.step != 1:
 raise ValueError("unsupported stepped range")
 return range1.stop > range2.start and range2.stop > range1.start
def intersect(range1: range, range2: range) \
 -> tuple[Optional[range], Sequence[range], Sequence[range]]:
 """Given two ranges, returns:
 1. the eventual intersection of both ranges;
 2. parts of the first range that are not part of the second one;
 3. parts of the second range that are not part of the first one.
 """
 if range1.start >= range1.stop or range2.start >= range2.stop:
 raise ValueError("usupported empty range") 
 if range1.step != 1 or range2.step != 1:
 raise ValueError("unsupported stepped range")
 if not intersects(range1, range2):
 # Disjoint ranges
 return None, (range1,), (range2,)
 diff1: list[range] = []
 if range1.start < range2.start:
 diff1.append(range(range1.start, range2.start))
 if range2.stop < range1.stop:
 diff1.append(range(range2.stop, range1.stop))
 diff2: list[range] = []
 if range2.start < range1.start:
 diff2.append(range(range2.start, range1.start))
 if range1.stop < range2.stop:
 diff2.append(range(range1.stop, range2.stop))
 return (range(max(range1.start, range2.start),
 min(range1.stop, range2.stop)),
 diff1, diff2)