Counting Disk Intersections using TreeSet

A different algorithm (O(N log N)):

This bad drawing of the scenario:

Can be translated into a list of ranges: (not exactly the same scenario)

Fig. 2

O(N log N): We first sort the markers, taking care that green markers appear before red ones if we want to count tangent discs as overlaps.

O(N): We scan from left to right, with total initially = 0 and overlaps initially = 0. Every time we hit a green marker, total += 1, and at every red marker, total -= 1. Additionally, at each green marker, if total > 0, then overlaps += total.

The black numbers in Fig. 2 are total at each step; orange is overlaps.

Then overlaps should be the answer.

See a crude implementation here: http://ideone.com/ggiRPA

There is a simpler way...

1. Create 2 arrays of N elements (leftEdge, rightEdge).
2. For each element calculate left and right edge (index -/+ value) and set it in arrays.
3. Sort arrays.
4. For each element in rightEdge array loop through leftEdge array to find first greater or equal element. Save number of remaining elements and current index. For next element start loop from saved index...

This way we really loop through each sorted array only once, so algorithm's complexity is O(N log N).