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
Post a Comment