compress.py

class Range(object):
    'An object with a start and a length.'

    def __init__(self, start, length):
        self.start = start
        self.length = length

    def contains(self, another):
        'If the range contains another range.'
        return another.start >= self.start and \
            another.start < self.start + self.length

    def merge(self, another):
        'Merge another range.'
        self.start = min(self.start, another.start)
        self.length = max(self.start + self.length,
                          another.start + another.length) - self.start


def solve(data):
    ranges = [Range(x[0], x[1]) for x in data]
    results = []
    buffer = None
    for aRange in ranges:
        if buffer == None:
            buffer = aRange
            continue
        if buffer.contains(aRange):
            buffer.merge(aRange)
        else:
            results.append(buffer)
            buffer = aRange
    if buffer != None:
        results.append(buffer)
    return [(x.start, x.length) for x in results]


if __name__ == '__main__':
    results = solve([])
    assert(results == [])

    results = solve([(1, 1)])
    assert(results == [(1, 1)])

    results = solve([(1, 1), (3, 2)])
    assert(results == [(1, 1), (3, 2)])

    results = solve([(1, 4), (2, 5)])
    assert(results == [(1, 6)])

    results = solve([(1, 4), (2, 5), (7, 4), (8, 5)])
    assert(results == [(1, 6), (7, 6)])

    results = solve([(1, 4), (2, 5), (6, 4), (8, 5)])
    assert(results == [(1, 12)])