Compute the number of intersections in a sequence of discs. follows the solution described here: http://stackoverflow.com/questions/4801242/algorithm-to-calculate-number-of-intersecting-discs

NumberOfDiscIntersections.py

def solution(A):
    # write your code in Python 2.7
    B = []
    for i in xrange(len(A)):
        B.append((i-A[i],i+A[i]))
    B = sorted(B, key=lambda x:x[0])
    cnt = 0
    for i in xrange(len(A)-1):
        right = B[i][1]
        start = i+1
        end = len(A)-1
        res = i
        while start <=end:
            mid = (start+end)/2
            if B[mid][0] <= right:
                start = mid+1
                res = mid
            else:
                end = mid-1
        cnt +=(res - i)
    if cnt > 10000000:
        return -1
    return cnt