python - Find all possible overlap and non-overlaps from list of various ranges of numbers -

with following code can determine overlap range, give list of ranges (tuple). list size can vary. example list has 3 tuples.

ranges = [(10,20), (15,25), (18,30)] starts, ends = zip(*ranges) result = range(max(starts), min(ends) + 1) print(*result) # 18 19 20 

now want find non-overlap. same input ranges. yields:

(10,11,12,13,14) (26,27,28,29,30) 

how can achieve that?

here's solution using heapq:

range(*heapq.nsmallest(2, starts))   # -> 10, 11, 12, 13, 14 end, start = heapq.nlargest(2, ends) range(start+1, end)   # 26, 27, 28, 29, 30 

note work if overlap non-empty.

when have empty overlap can obtain "non-overlap" doing:

range(min(starts), max(ends)) 

i.e. it's whole range.

so, if wanted function you'd get:

def find_overlap_and_non_overlap(ranges):     starts, ends = zip(*ranges)     overlap = range(max(starts), min(ends)+1)     if not overlap:         return ([], range(min(starts), max(ends)+1), [])      less_non_overlap = range(*heapq.nsmallest(2, starts))     end, start = heapq.nlargest(2, ends)     greater_non_overlap = range(start+1, end+1)     return (overlap, less_non_overlap, greater_non_overlap) 

which sample input returns:

in[5]: find_overlap_and_non_overlap(ranges) out[5]: (range(18, 21), range(10, 15), range(26, 31)) in [6]: list(map(list, find_overlap_and_non_overlap(ranges))) out[6]: [[18, 19, 20], [10, 11, 12, 13, 14], [26, 27, 28, 29, 30]] 

the first element overlapping values, second non-overlapping values come before overlap , last element non-overlapping values come after overlap. if overlap empty values put in second element of tuple.

---

if want obtain overlap/non-overlap of pairs of ranges can repeatedly call function:

results = []  in ranges:     b in ranges:         if != b:             results.append(find_overlap_and_non_overlap([a, b]))