phillydev#daily_programmer-2017-03-29.py

overlaps.py

def overlaps(pairs):
    clusters = []
    for pair in sorted(pairs):
        low, high = pair
        found = False
        for i, cluster in enumerate(clusters):
            cluster_low, cluster_high = cluster
            if max(low, cluster_low) <= min(high, cluster_high):
                found = True
                clusters[i] = [min(low, cluster_low), max(high, cluster_high)]
                break;
        if not found:
            clusters.append(pair)
    return clusters

if __name__ == '__main__':
    examples = [
        ([[1,3], [2,6], [8,10], [7,11]], [[1,6], [7,11]]),
        ([[5,12], [8,10]],[[5,12]]),
        ([[1,3], [2,6], [8,10], [7,11], [6,9]], [[1,11]]),
    ]    
    for example in examples:
        data, result = example
        assert overlaps(data) == result, "got {0} expected {1}".format(overlaps(data), result)