https://stackoverflow.com/questions/43600878/merging-overlapping-intervals https://stackoverflow.com/questions/23639361/fast-checking-of-ranges-in-python

range_operations.py

from bisect import bisect
from more_itertools import flatten

def merge_overlapping_spans(spans):
    spans = map(list, spans)
    spans = sorted(spans, key=lambda x: x[0])
    merged = [spans[0]]
    for current in spans:
        previous = merged[-1]
        if current[0] <= previous[1]:
            previous[1] = max(previous[1], current[1])
        else:
            merged.append(current)
    return list(map(tuple, merged))

def indices_not_in_spans(indices, spans):
    merged_feature_spans = merge_overlapping_spans(spans)
    boundaries = list(flatten([[s, e+1] for s, e in merged_feature_spans]))
    excluded_spans = [n for n in indices if bisect(boundaries, n) % 2 == 0]
    return excluded_spans