Pastebin launched a little side project called VERYVIRAL.com, check it out ;-) Want more features on Pastebin? Sign Up, it's FREE!
Guest

Disk Intersections

By: a guest on Dec 26th, 2012  |  syntax: Java  |  size: 0.86 KB  |  views: 488  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. import java.util.*;
  2.  
  3. class Solution {
  4.   public int number_of_disc_intersections ( int[] A ) {
  5.     int overlaps = 0;
  6.     if (A.length<2) return 0;
  7.     PriorityQueue<Integer> leftEdges = new PriorityQueue<Integer>();
  8.     PriorityQueue<Long> rightEdges = new PriorityQueue<Long>();
  9.     for (int i=0; i<A.length; i++){
  10.       leftEdges.add(i-A[i]);
  11.       rightEdges.add((long)i+(long)(A[i]));
  12.     }
  13.     int otherCirclesAtThisEdgeNum = 0;
  14.     while ( !rightEdges.isEmpty()) {
  15.       try {
  16.         if (leftEdges.element() <= rightEdges.peek() ) {
  17.           overlaps += otherCirclesAtThisEdgeNum++;
  18.           if (overlaps > 10000000) return -1;
  19.           leftEdges.poll();
  20.         } else {
  21.           otherCirclesAtThisEdgeNum--;
  22.           rightEdges.poll();
  23.         }
  24.       }catch (NoSuchElementException e){
  25.         break;
  26.       }
  27.     }
  28.     return overlaps;
  29.   }
  30. }