Skip to content

Instantly share code, notes, and snippets.

@xeonqq
Created September 4, 2015 16:13
Show Gist options
  • Save xeonqq/efb4a662ab8f52f36f49 to your computer and use it in GitHub Desktop.
Save xeonqq/efb4a662ab8f52f36f49 to your computer and use it in GitHub Desktop.
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
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment