У нас может быть простой, O (n) временной интервал O (1), алгоритм для отслеживания интервала, в котором мы находимся, когда мы перебираем интервалы, отсортированные по начальной позиции.Текущий интервал начинается с:
left = interval[0][0]
right = interval[0][1]
i = 1 // pointer
n = list length
max_gap = 0
Затем,
while i < n and interval[i][0] <= right:
// update right
right = max(right, interval[i][1])
i = i + 1
Теперь мы либо в конце списка, если не было пробелов, либо мы в новом интервале, которыйначался по крайней мере с (right + 1) (который, я думаю, в вашем случае не будет рассматриваться как пробел).
Итак, обновите текущий самый большой пробел и повторите процедуру while.
max_gap = max(
max_gap,
interval[i][0] - right - 1
)
left = interval[i][0]
right = interval[i][1]
Пример JavaScript:
function f(A){
console.log(JSON.stringify(A))
let left = A[0][0]
let right = A[0][1]
console.log(`i: 0, (${ left }, ${ right })`)
let i = 1 // pointer
let n = A.length
let max_gap = 0
while (i < n){
while (i < n && A[i][0] <= right){
// update right
right = Math.max(right, A[i][1])
console.log(`i: ${ i }, (${ left }, ${ right })`)
i = i + 1
}
if (i < n){
max_gap = Math.max(
max_gap,
A[i][0] - right - 1
)
console.log(`i: ${ i }, max_gap: ${ max_gap }`)
left = A[i][0]
right = A[i][1]
}
}
return max_gap
}
let examples = [
[[1,5], [2,4], [6,10], [6,8]],
[[1, 2], [2, 2], [5, 6], [8, 10]],
[[2,4], [5,8], [9,10]],
[[1,1], [5,6], [9,10]]
]
for (let ex of examples)
console.log(`result: ${ f(ex) }\n\n`)