[Codility] (Lesson6 | Sorting) NumberOfDiscIntersections - JavaScript

質問する

We draw N discs on a plane. The discs are numbered from 0 to N − 1. An array A of N non-negative integers, specifying the radiuses of the discs, is given. The J-th disc is drawn with its center at (J, 0) and radius A[J].
We say that the J-th disc and K-th disc intersect if J ≠ K and the J-th and K-th discs have at least one common point (assuming that the discs contain their borders).
The figure below shows discs drawn for N = 6 and A as follows:
A[0] = 1
A[1] = 5
A[2] = 2
A[3] = 1
A[4] = 4
A[5] = 0

There are eleven (unordered) pairs of discs that intersect, namely:
discs 1 and 4 intersect, and both intersect with all the other discs;
disc 2 also intersects with discs 0 and 3.
Write a function:
function solution(A);
that, given an array A describing N discs as explained above, returns the number of (unordered) pairs of intersecting discs. The function should return −1 if the number of intersecting pairs exceeds 10,000,000.
Given array A shown above, the function should return 11, as explained above.
Write an efficient algorithm for the following assumptions:
N is an integer within the range [0..100,000];
each element of array A is an integer within the range [0..2,147,483,647].

もんだいぶんせき

配列Aをx軸に丸めたものと考える.配列Aのインデックスは円の中心軸であり、値は半径である.配列Aの内容をもとにx軸に円を描くときに重なる円の個数を求める.重複する個数が1000000個を超える場合は-1を返し、この値を下回る場合は個数を返します.

問題を解く

Aの半径を

で並べ、地図で円の両端を求める配列を描きます.中心軸はインデックス値なので、円の左の値は인덱스 값 - 반지름、右の値は인덱스 + 반지름です.

sortを使用して、左の値が等しくない場合は左の値で昇順にソートし、等しい場合は右の値で降順にソートします.

このソートは、左円から比較することを意味し、左円の値が同じであれば、先により大きな円を比較することを意味する.

が重なる円を探すので、基準となる円arr[i]と比較した円arr[j]は、arr[j]の左の値がarr[i]の左の値より大きく、右の値が小さいことを確認し、基準円内に比較した円があることを導く.

オーバラップリングの個数を加算し、1000000より大きい場合は-1を返し、オーバラップしない場合は割込みにより効率を向上させる.

コード#コード#

function solution(A) {
    // write your code in JavaScript (Node.js 8.9.4)
    let answer = 0;
    let arr = A.map((v,i)=>[i-v,i+v]);
    arr.sort((a,b)=>{
        if(a[0]!==b[0]) return a[0]-b[0]
        else return b[1]-a[1]
    });

    for(let i = 0; i<arr.length; i++){
        for(let j = i+1; j<arr.length; j++){
            if(arr[i][0] <= arr[j][0] && arr[i][1] >= arr[j][0]) answer++
            else break;
            if(answer>10000000) return answer = -1
        }
    }
    
    return answer
}

最終結果

ソース

https://app.codility.com/programmers/lessons/6-sorting/