Конвертировать массив пересекающихся интервалов в массив не пересекающихся?

Question

[token]

Привет эксперты!


Вопрос: имеется массив пересекающихся интервалов:

var ranges = [{<br/>
 &quot;from&quot;: 0,<br/>
 &quot;to&quot;: 100<br/>
}, {<br/>
 &quot;from&quot;: 50,<br/>
 &quot;to&quot;: 200<br/>
}, {<br/>
 &quot;from&quot;: 0,<br/>
 &quot;to&quot;: 100<br/>
}, {<br/>
 &quot;from&quot;: 70,<br/>
 &quot;to&quot;: 200<br/>
}, {<br/>
 &quot;from&quot;: 90,<br/>
 &quot;to&quot;: 300<br/>
}];

Мне необходимо сконвертировать его в массив не пересекающихся интервалов, т. е.:

var nonOverlapping = splitRanges(ranges);<br/>
<br/>
/*<br/>
nonOverlapping = [{<br/>
 &quot;from&quot;: 0,<br/>
 &quot;to&quot;: 49<br/>
}, {<br/>
 &quot;from&quot;: 50,<br/>
 &quot;to&quot;: 69<br/>
}, {<br/>
 &quot;from&quot;: 70,<br/>
 &quot;to&quot;: 89<br/>
}, {<br/>
 &quot;from&quot;: 90,<br/>
 &quot;to&quot;: 100<br/>
}, {<br/>
 &quot;from&quot;: 101,<br/>
 &quot;to&quot;: 200<br/>
}, {<br/>
 &quot;from&quot;: 201,<br/>
 &quot;to&quot;: 300<br/>
}]<br/>
*/

У меня есть функция которая выполняет это, но использует она так называемый «naive approach» (крайне неэффективное решение):

function splitRanges(ranges) {<br/>
 var repeat, length, i, j;<br/>
 var rangeA, rangeB, intersection;<br/>
 do {<br/>
 repeat = false;<br/>
 length = ranges.length;<br/>
 for (i = 0; i &lt; length; i++) {<br/>
 rangeA = ranges[i];<br/>
 for (j = i + 1; j &lt; length; j++) {<br/>
 rangeB = ranges[j];<br/>
 if (isIntersectingRanges(rangeA, rangeB)) {<br/>
 repeat = true;<br/>
 ranges.splice(i, 1);<br/>
 intersection = splitRange(rangeA, rangeB);<br/>
 while (intersection.length) {<br/>
 ranges.push(intersection.shift());<br/>
 }<br/>
 }<br/>
 if (repeat) break;<br/>
 }<br/>
 if (repeat) break;<br/>
 }<br/>
 } while (repeat);<br/>
}

Мог бы кто — нибудь помочь мне переписать это так чтобы решение было оптимальным с точки зрения быстродействия?

Answer 1

[VladX]

Складываете все численные значения from и to в один массив, при этом в этом массиве должны лежать пары (граница, тип), где тип — это значение типа boolean (например, true — это левая граница (from), а false — правая (to)).
Затем запускаете алгоритм быстрой сортировки на массиве.
Затем, FOR-ом проходите по отсортированному массиву и формируете окончательный список. Список формируется примерно так: проверяем тип границы, добавляем границу в список, идём дальше. Если несколько раз подряд встречается граница одного типа, то имеет место пересечение. В этом случае для левой границы нужно запоминать только первый встретившийся элемент, а для правой — последний.
Вот как-то так. Если не понятно объяснил, спрашивайте.

Алгоритм работает примерно за O(N log(N) + N) = O(N log(N)), т.е. довольно быстро.

Comments

[token]

Спасибо! Вроде бы ясно и просто, вечером попробую воплотить, о результатах отпишусь. Спасибо.

[VladX]

Да, кстати, забыл написать: для алгоритма, который я привёл, важно, чтобы не было нулевых интервалов (from == to), иначе он будет работать неверно.

[token]

Тогда в свою очередь и я забыл сказать что в моей задаче такие интервалы могут быть…

[VladX]

А вам важно учитывать пустые промежутки? Если нет, тогда в самом начале просто удалите их. Если да, то во время сортировки нужно учитывать, что при совпадении границы первыми в массиве должны идти левые границы, а потом уже правые.

[token]

Попробовал, с незначительными изменениями это заработало. Теперь не пойму как мне расширить этот алгоритм чтобы он мне возвращал еще и id'шники пересекшихся интервалов? т. е.:

var ranges = [{
"id": 1,
"from": 0,
"to": 100
}, {
"id": 2,
"from": 30,
"to": 30
}, {
"id": 3,
"from": 50,
"to": 200
}, {
"id": 4,
"from": 0,
"to": 100
}, {
"id": 5,
"from": 70,
"to": 200
}, {
"id": 6,
"from": 90,
"to": 300
}]

Результатом должен стать массив интервалов выглядящий вот так:

var nonOverlapping = [{
"id": 1,
"from": 0,
"to": 29
}, {
"id": 4,
"from": 0,
"to": 29
}, {
"id": 1,
"from": 30,
"to": 30
}, {
"id": 2,
"from": 30,
"to": 30
}, {
"id": 4,
"from": 30,
"to": 30
}, {
"id": 1,
"from": 31,
"to": 49
}, {
"id": 4,
"from": 31,
"to": 49
}, {
"id": 1,
"from": 50,
"to": 69
}, {
"id": 3,
"from": 50,
"to": 69
}, {
"id": 4,
"from": 50,
"to": 69
}, {
"id": 3,
"from": 70,
"to": 89
}, {
"id": 4,
"from": 70,
"to": 89
}, {
"id": 5,
"from": 70,
"to": 89
}, {
"id": 1,
"from": 70,
"to": 89
}, {
"id": 3,
"from": 90,
"to": 100
}, {
"id": 4,
"from": 90,
"to": 100
}, {
"id": 5,
"from": 90,
"to": 100
}, {
"id": 6,
"from": 90,
"to": 100
}, {
"id": 1,
"from": 90,
"to": 100
}, {
"id": 3,
"from": 101,
"to": 200
}, {
"id": 5,
"from": 101,
"to": 200
}, {
"id": 6,
"from": 101,
"to": 200
}, {
"id": 6,
"from": 201,
"to": 300
}]

Алгоритм:

var result = [];
var firstItem = null;

for (var c = 0; c < items.length; c++) {

if (!firstItem) {
firstItem = items[c];
} else if (firstItem.value === items[c].value) {
if (firstItem.type !== items[c].type) {
result.push({
from: firstItem.value,
to: items[c].value
});
firstItem = items[c];
} else {
}
} else if (firstItem.type === 'start' && items[c].type === 'start') {
result.push({
from: firstItem.value,
to: items[c].value - 1
});
firstItem = items[c];
} else if (firstItem.type === 'start' && items[c].type === 'end') {
result.push({
from: firstItem.value,
to: items[c].value
});
firstItem = items[c];
} else if (firstItem.type === 'end' && items[c].type === 'end') {
result.push({
from: firstItem.value + 1,
to: items[c].value
});
firstItem = items[c];
} else if (firstItem.type === 'end' && items[c].type === 'start') {
result.push({
from: firstItem.value + 1,
to: items[c].value - 1
});
firstItem = items[c];
}
}