Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.*;
- class Solution {
- public int number_of_disc_intersections ( int[] A ) {
- int overlaps = 0;
- if (A.length<2) return 0;
- PriorityQueue<Integer> leftEdges = new PriorityQueue<Integer>();
- PriorityQueue<Long> rightEdges = new PriorityQueue<Long>();
- for (int i=0; i<A.length; i++){
- leftEdges.add(i-A[i]);
- rightEdges.add((long)i+(long)(A[i]));
- }
- int otherCirclesAtThisEdgeNum = 0;
- while ( !rightEdges.isEmpty()) {
- try {
- if (leftEdges.element() <= rightEdges.peek() ) {
- overlaps += otherCirclesAtThisEdgeNum++;
- if (overlaps > 10000000) return -1;
- leftEdges.poll();
- } else {
- otherCirclesAtThisEdgeNum--;
- rightEdges.poll();
- }
- }catch (NoSuchElementException e){
- break;
- }
- }
- return overlaps;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement