Google : Find intersected circles

Given an array A of N integers we draw N discs in a 2D plane, such that i-th disc has
center in (0,i) and a radius A[i]. We say that k-th disc and j-th disc intersect,
if $k\not =j$ and k-th and j-th discs have at least one common point.
Write a function
class Solution { public int number_of_disc_intersections(int[] A); }
which given an array A describing N discs as explained above, returns the number of
pairs of intersecting discs. For example, given N=6 and
\begin{displaymath}A[0]=1 A[1]=5 A[2]=2 A[3]=1 A[4]=4 A[5]=0\end{displaymath}
there are 11 pairs of intersecting discs:
0th and 1st
0th and 2nd
0th and 4th
1st and 2nd
1st and 3rd
1st and 4th
1st and 5th
2nd and 3rd
2nd and 4th
3rd and 4th
4th and 5th
so the function should return 11.
The function should return -1 if the number of intersecting pairs exceeds 10,000,000.
The function may assume that N does not exceed 10,000,000.

实际上这道题就是求线段重叠的问题， 不过这里有一个很方便的计算线段重叠的方法：
1 把所有线段的两个端点拆开，合并并排序， 注意要记录端点是启始点还是终结点
2 从小到大遍历这些端点，通过下面这个算法计算重叠：
int nCount = 0;
        int nRet = 0;
        for (vector<END>::iterator it = vec.begin();
                it != vec.end(); it++)
        {
                if (it->bLft) // start point
                        nCount++;
                else // end point
                {
                        nCount--;
                        nRet += nCount;
                }
        }

1. 
   
2. struct END
   
3. {
   
4.         int nVal;
   
5.         bool bLft;
   
6. };
   
7. 
   
8. bool LessThan(const END& a, const END& b)
   
9. {
   
10.         return a.nVal < b.nVal;
    
11. }
    
12. 
    
13. int GetIntersections(int A[], int n)
    
14. {
    
15.         assert(A && n > 0);
    
16. 
    
17.         vector<END> vec;
    
18.         for (int i = 0; i < n; i++)
    
19.         {
    
20.                 END ed1, ed2;
    
21. 
    
22.                 ed1.nVal = i - A[i];
    
23.                 ed1.bLft = true;
    
24.                 ed2.nVal = i + A[i];
    
25.                 ed2.bLft = false;
    
26. 
    
27.                 vec.push_back(ed1);
    
28.                 vec.push_back(ed2);
    
29.         }
    
30. 
    
31.         sort(vec.begin(), vec.end(), LessThan);
    
32. 
    
33.         int nCount = 0;
    
34.         int nRet = 0;
    
35.         for (vector<END>::iterator it = vec.begin();
    
36.                 it != vec.end(); it++)
    
37.         {
    
38.                 if (it->bLft) // start point
    
39.                         nCount++;
    
40.                 else // end point
    
41.                 {
    
42.                         nCount--;
    
43.                         nRet += nCount;
    
44.                 }
    
45.         }
    
46. 
    
47.         return nRet;
    
48. }
    

复制代码

回复 2# wwwyhx
这方法还挺巧的，排完虚之后O(n)就可以了。之前见过类似的题目我能想到的就是先把线段按起始位置排序，然后对于每个线段segment[ i ]，在它后面的线段中找到第一个起始位置大于segment[ i ].end的线段，把中间的线段全count进去。查找可以二分，总的复杂度也是O(nlogn)。

LZ的方法好机智！！！太聪明了

这坟挖的……
这个想法不错，但是代码错了吧？在比较函数那里，如果两个点的nVal相等，应该是bLft==true的排在前面

ccarter 发表于 2016-3-23 04:51
这坟挖的……
这个想法不错，但是代码错了吧？在比较函数那里，如果两个点的nVal相等，应该是bLft==true的 ...

对哈！！ 多亏你指出来，我都忽视这点了！