【题解】【区间】【Sorting】【Codility】Number of disc intersections

Given an array A of N integers, we draw N discs in a 2D plane such that the I-th disc is centered on (0,I) and has a radius of A[I]. We say that the J-th disc and K-th disc intersect if J ≠ K and J-th and K-th discs have at least one common point.

Write a function:

int solution(const vector<int> &A);

that, given an array A describing N discs as explained above, returns the number of pairs of intersecting discs. For example, given N=6 and:

 

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

 

intersecting discs appear in eleven pairs of elements:

• 0 and 1,
• 0 and 2,
• 0 and 4,
• 1 and 2,
• 1 and 3,
• 1 and 4,
• 1 and 5,
• 2 and 3,
• 2 and 4,
• 3 and 4,
• 4 and 5.

so the function should return 11.

The function should return ?1 if the number of intersecting pairs exceeds 10,000,000.

Assume that:

• N is an integer within the range [0..100,000];
• each element of array A is an integer within the range [0..2147483647].

Complexity:

• expected worst-case time complexity is O(N*log(N));
• expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified.

思路：

这题是Codility Sorting一章的三星题beta2010，思路是

1 将圆抽象成区间，可以看做

2 把区间的进入作为一个事件，出去作为一个事件。

3 O(n)扫一遍，累计+1或者-1当前重叠的区间，就可以得到结果。

4 注意的是A[i]+i可能会超出int。 

刚开始我的思路是

1 将圆抽象成区间

2 对区间进行排序

3 遍历序列，二分查找跟当前区间相交的区间数量

这个做法也是 O(N*log(N))，不过就没那么聪明了

 1 int solution(const vector<int> &A) {
 2     vector<pair<long long, int> > intervals;
 3     for (int i = 0; i < A.size(); i++) {
 4         intervals.push_back(make_pair(((long long)i)-A[i], 0));//先进后出
 5         intervals.push_back(make_pair(((long long)i)+A[i], 1));
 6     }
 7     sort(intervals.begin(), intervals.end());
 8     int res = 0;
 9     int height = 0;
10     for (vector<pair<long long, int> >::iterator it = intervals.begin(); it != intervals.end();it++) {
11         if (it->second == 0) { // start point
12             res += height++;
13             if (res > 10000000) return -1;
14         }
15         else { // end point
16             height--;
17         }
18     }
19     return res;
20 }

【题解】【区间】【Sorting】【Codility】Number of disc intersections

原文：http://www.cnblogs.com/wei-li/p/Numberofdiscintersections.html