NumberOfDiscIntersections

NumberOfDiscIntersections.js

function solution(A) { // [1,5,2,1,4,0]
    var starts = []; // disk start points
    var ends = [];   // disk end points
    for (var i=0; i<A.length; i++) {
        starts.push(i - A[i]); // [-1, -4, 0, 2, 0, 5]
        ends.push(i + A[i]);   // [1,   6, 4, 4, 8, 5]
    }
    starts.sort( (a,b) => a-b) // [ -4, -1, 0, 0, 2, 5 ]
    ends.sort( (a,b) => a-b) // [ 1, 4, 4, 5, 6, 8 ]

    let endNdx = 0; // position of ends
    let od = 0;     // number of opened disks
    let nts = 0;    // number of intersections
    let end = ends[endNdx];

    for (var i=0; i<starts.length; i++) {
        const sta = starts[i];
        if (sta <= end) {
            nts += od;
            od++;
            // console.log(1, {sta, end, nts, od})
        } else {
            // console.log(2, {sta, end, nts, od})
            do {
                od--;
                end = ends[++endNdx];
                // console.log(3, {sta, end, nts, od})
            } while( sta > end); // until opens a disk
            nts += od;
            od++;
            // console.log(4, {sta, end, nts, od})
        }
        if (nts > 10000000) 
            return -1;
    }
    return nts;
}

/* 
-4   1         nts 0   od 1
-1   1         nts 1   od 2
 0   1         nts 3   od 3
 0   1         nts 6   od 4
 2   1         nts 6.  od 3
  2  4         nts 9.  od 4
 5   4         nts 9.  od 3   
 5   4         nts 9.  od 2
 5   5         nts 11  od 2
 */