def merge(xs):
    xs.sort()
    result = xs[0:1]
    for a, b in xs[1:]:
        y, z = result[-1]
        if a <= z:
            result[-1] = (y, max(b, z))
        else:
            result.append((a, b))
    return result

inputs = [([(0,1),(3,5),(4,8),(10,12),(9,10)], [(0,1),(3,8),(9,12)]),
          ([(1,2),(2,3)], [(1,3)]),
          ([(1,5),(2,3)], [(1,5)]),
          ([(1,10),(2,6),(3,5),(7,9)], [(1,10)]),
          ]
for x, expected in inputs:
    result = merge(x)
    print(x)
    print(result)
    assert result == expected
    print("Success!")