language agnostic - Algorithm to calculate number of intersecting discs -


given array a of n integers draw n discs in 2d plane, such i-th disc has center in (0,i) , radius a[i]. k-th disc , j-th disc intersect, if k-th , j-th discs have @ least 1 common point.

write function

int number_of_disc_intersections(int[] a); 

which given array a describing n discs explained above, returns number of pairs of intersecting discs. example, given n=6 ,

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

there 11 pairs of intersecting discs:

0th , 1st 0th , 2nd 0th , 4th 1st , 2nd 1st , 3rd 1st , 4th 1st , 5th 2nd , 3rd 2nd , 4th 3rd , 4th 4th , 5th 

so function should return 11. function should return -1 if number of intersecting pairs exceeds 10,000,000. function may assume n not exceed 10,000,000.

so want find number of intersections of intervals [i-a[i], i+a[i]].

maintain sorted array (call x) containing i-a[i] (also have space has value i+a[i] in there).

now walk array x, starting @ leftmost interval (i.e smallest i-a[i]).

for current interval, binary search see right end point of interval (i.e. i+a[i]) go (called rank). know intersects elements left.

increment counter rank , subtract current position (assuming 1 indexed) don't want double count intervals , self intersections.

o(nlogn) time, o(n) space.


Comments

Popular posts from this blog

java - SNMP4J General Variable Binding Error -

windows - Python Service Installation - "Could not find PythonClass entry" -

Determine if a XmlNode is empty or null in C#? -