Number of disc intersections (Problem in sorting and searching)

Problem
    

Number Of Disc Intersections: Compute the number of intersections in a sequence of discs.

We draw N discs on a plane. The discs are numbered from 0 to N − 1. An array A of N non-negative integers, specifying the radiuses of the discs, is given. The J-th disc is drawn with its center at (J, 0) and radius A[J].

We say that the J-th disc and K-th disc intersect if J ≠ K and the J-th and K-th discs have at least one common point (assuming that the discs contain their borders).

The figure below shows discs drawn for N = 6 and A as follows:

    A[0] = 1
    A[1] = 5
    A[2] = 2
    A[3] = 1
    A[4] = 4
    A[5] = 0

There are eleven (unordered) pairs of discs that intersect, namely:

discs 1 and 4 intersect, and both intersect with all the other discs;
disc 2 also intersects with discs 0 and 3.
Write a function in Java with following signature:

class Solution { public int solution(int[] A); }

And in Python with following signature:

def solution(A):

that, given an array A describing N discs as explained above, returns the number of (unordered) pairs of intersecting discs. The function should return −1 if the number of intersecting pairs exceeds 10,000,000.

Given array A shown above, the function should return 11, as explained above.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [0..100,000];
each element of array A is an integer within the range [0..2,147,483,647].

Solution

WITHOUT BINARY SEARCH

Task Score: 62%

Correctness: 100%

Performance: 25%

~~~

def solution(A):
    # Implement your solution here

    # Get the start and end indices of the disks and sort them based on the start indices

    start_and_end = []
    for i in range(len(A)):
        temp = {
            'start': i - A[i],
            'end': i + A[i]
        }
        start_and_end.append(temp)

    start_and_end.sort(key = lambda d: d['start'])

    # Search for the starting index bigger than the current end index

    intersections = []
    for i in range(len(start_and_end)):
        end = start_and_end[i]['end']
        cnt_intersections = 0    
        for j in range(i+1, len(start_and_end)):
            if start_and_end[j]['start'] <= end:
                cnt_intersections += 1
            else:
                break
        intersections.append(cnt_intersections)
    return sum(intersections)


Ref