编码测试中的盘交叉点数超时

Question

我的代码传递正确，但对于具有大量交集的输入数组，它会超时。

盘数交叉点

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

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)

用"开始"和"结束"拆分并标记间隔，然后对它们进行排序：

(-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