代码测试中的NumberOfDiscIntersections超时

Question

我的代码被认为是正确的，但是对于交集数量非常多的输入数组，它会超时。

NumberOfDiscIntersections

如何才能降低解决方案的复杂性并使其更高效？

function solution(A) {
    let ret = 0;
    for(let i = 0; i < A.length; i++){
        const a = A[i];
        for(let j = i+1; j < A.length; j++){
            const b = A[j];
            if(i+a >= j-b){
                ret++;
                if(ret > 10000000){
                    return -1;
                }
            }
        }
    }
    return ret;
}

Answer 1

获取间隔：

A[0] = 1 -> (-1, 1)
A[1] = 5 -> (-4, 6)
A[2] = 2 -> (0, 4)
A[3] = 1 -> (2, 4)
A[4] = 4 -> (0, 8)
A[5] = 0 -> (5, 5)

拆分间隔，并用"start“和"end”标记间隔，然后对它们进行排序：

(-4s,6e) (-1s,1e) (0s,4e) (0s,8e) (2s,4e) (5s,5e)

-4s -1s 0s 0s 1e 2s 4e 4e 5s 5e 6e 8e

s means start
e means end

从左到右迭代，保持静止打开间隔的计数，并添加与当前起始点重叠的仍然打开的间隔的数量。

     open  overlaps
-4s:   1     0
-1s:   2     1
 0s:   3     2
 0s:   4     3
 1e:   3
 2s:   4     3
 4e:   3
 4e:   2
 5s:   3     2
 5e:   2
 6e:   1
 8e:   0
 
 Total       11