使用TreeSet计算磁盘交叉点

Question

在我将真实测试作为工作申请的一部分之前,我正在尝试Codility的演示问题.他们的演示之一是涉及计算磁盘阵列的磁盘交叉点数量的问题.

任务描述是

给定N个整数的阵列A,我们在2D平面中绘制N个盘,使得第I个盘以(0,I)为中心并且具有A [I]的半径.我们说如果J≠K并且第J和第K个盘具有至少一个公共点,则第J个盘和第K个盘相交.编写函数:class Solution {public int number_of_disc_intersections(int [] A); 如上所述,给定描述N个盘的阵列A,返回交叉盘对的数量.

您可以在此处查看测试.

有一些明显的O(n ^ 2)时间复杂度解决方案,但目标是O(n*log(n)).

我想出了这个,它适用于我提供的任何示例,以及由codility([1,5,2,1,4,0​​])给出的简单测试用例,但Codility告诉我它在大多数情况下都失败了其他但我不明白为什么.

这当然应该是为O(n log n)的作为将每个n个磁盘到一个TreeSet的是数N,然后我们通过每个盘走,只有O(1)操作TreeSet.headSet().

import java.util.*;

class Circle implements Comparable<Circle> {
  long edge;
  int index;

  Circle (long e, int i){
    edge = e;
    index = i;
  }

  long getRightAssumingEdgeIsLeft(){
    return (long)(2*index - edge + 1);
  }

  @Override
  public int compareTo(Circle other){
    return Long.valueOf(edge).compareTo(other.edge);
  }
}

class Solution {
  public int number_of_disc_intersections ( int[] A ) {
    int N = A.length;
    if (N<2) return 0;
    int result = 0;

    SortedSet<Circle> leftEdges  = new TreeSet<Circle>();
    for (int i=0; i<N; i++) {
      leftEdges.add( new Circle( (long)(i-A[i]), i ) );
    }
    int counter = 0;
    for (Circle c : leftEdges) {
      long rightEdge = c.getRightAssumingEdgeIsLeft();
      Circle dummyCircle = new Circle (rightEdge, -1);
      SortedSet<Circle> head = leftEdges.headSet(dummyCircle);
      result +=  head.size() - counter;
      if (result > 10000000) return -1;
      counter++;
    }
    return result;
  }
}

Answer 1

一种不同的算法(O(N log N)):

这个糟糕的情景图:

可以转换为范围列表:(不完全相同的场景)

图2

O(N log N):我们首先对标记进行排序,如果我们想将切线圆盘计算为重叠,请注意绿色标记出现在红色标记之前.

O(N):我们从total最初= 0和overlaps最初开始从左到右扫描= 0.每当我们点击绿色标记时,total += 1每个红色标记处,total -= 1.此外,在每个绿色标记,if total > 0, then overlaps += total.

图2中的黑色数字表示total每一步; 橙色是overlaps.

那overlaps应该是答案.

请参阅此处的粗略实现:http://ideone.com/ggiRPA