быстрый алгоритм для объединения перекрывающихся интервалов

Question

Я пытаюсь запрограммировать достаточно быстрый алгоритм для объединения интервалов со значениями.

Например, есть 3 интервала (включая от и до):

1. {from:1, to: 3, amount: 1}
2. {from:5, to: 7, amount: 1}
3. {from:2, to: 6, amount: 1}

Результат:

1. {from:1, to: 1, amount: 1}
2. {from:2, to: 3, amount: 2}
3. {from:4, to: 4, amount: 1}
4. {from:5, to: 6, amount: 2}
5. {from:7, to: 7,amount: 1}

Когда число интервалов достигает 5000, тогда вычисления в моем алгоритме может занять около минуты. (в случае, когда каждый новый интервал слияния перекрывает большое количество других). Может быть, кто-то может посоветовать какой-то уже известный алгоритм, подходящий для этой задачи, или, может быть, он уже столкнулся с подобной проблемой и поделится своим решением?

input result

       function mergeingIntervals(intervals: IInterval[]): IInterval[] {
            //sort by length
            intervals.sort((a, b) => b.to - b.from - a.to + a.from);
            const result = [intervals[0]];
            intervals.forEach(interval => addInterval(result, interval));
            result.sort((a, b) => a.from - b.from);

            return result;
        }

        function addInterval(result: IInterval[], interval: IInterval): void {
            const firstIntersectionIndex = result.findIndex(row =>
                row.from >= interval.from && row.to <= interval.to ||
                row.from >= interval.from && row.from <= interval.to ||
                row.from <= interval.from && row.to >= interval.to ||
                row.to >= interval.from && row.to <= interval.to,
            );

            if (firstIntersectionIndex === -1) {
                const indexToInsertInto = result.findIndex(row => row.from > interval.to);
                if (indexToInsertInto !== -1) {
                    result.splice(indexToInsertInto, 0, interval);
                } else {
                    result.unshift(interval);
                }
            } else {
                const valueToMergeInto = result[firstIntersectionIndex];
                if (valueToMergeInto.from <= interval.from && valueToMergeInto.to >= interval.to) {
                    const newIntervals: IInterval[] = [];
                    if (valueToMergeInto.from !== interval.from) {
                        newIntervals.push({
                            from: valueToMergeInto.from,
                            to: subtractHour(interval.from),
                            value: valueToMergeInto.value,
                        });
                    }
                    newIntervals.push({
                        from: interval.from,
                        to: interval.to,
                        value: interval.value + valueToMergeInto.value,
                    });
                    if (valueToMergeInto.to !== interval.to) {
                        newIntervals.push({
                            from: addHour(interval.to),
                            to: valueToMergeInto.to,
                            value: valueToMergeInto.value,
                        });
                    }
                    result.splice(firstIntersectionIndex, 1, ...newIntervals);
                } else {
                    let count = 1;
                    result.slice(firstIntersectionIndex).forEach(sumValue => {
                        if (sumValue.to <= interval.to) {
                            count++;
                            return false;
                        } else {
                            return true;
                        }
                    });
                    if (count < 5) {
                        result.splice(firstIntersectionIndex, 1);
                        const newIntervals: IInterval[] = [];
                        if (interval.from < valueToMergeInto.from) {
                            newIntervals.push({
                                from: interval.from,
                                to: subtractHour(valueToMergeInto.from),
                                value: interval.value,
                            }, {
                                from: valueToMergeInto.from,
                                to: Math.min(valueToMergeInto.to, interval.to),
                                value: valueToMergeInto.value + interval.value,
                            });
                            if (interval.to !== valueToMergeInto.to) {
                                newIntervals.push({
                                    from: addHour(Math.min(valueToMergeInto.to, interval.to)),
                                    to: Math.max(valueToMergeInto.to, interval.to),
                                    value: valueToMergeInto.to < interval.to ? interval.value : valueToMergeInto.value,
                                });
                            }
                        } else {
                            if (interval.from !== valueToMergeInto.from) {
                                newIntervals.push({
                                    from: valueToMergeInto.from,
                                    to: subtractHour(interval.from),
                                    value: valueToMergeInto.value,
                                });
                            }
                            newIntervals.push({
                                from: interval.from,
                                to: Math.min(interval.to, valueToMergeInto.to),
                                value: interval.value + valueToMergeInto.value,
                            });
                            if (interval.to !== valueToMergeInto.to) {
                                newIntervals.push({
                                    from: addHour(Math.min(valueToMergeInto.to, interval.to)),
                                    to: Math.max(valueToMergeInto.to, interval.to),
                                    value: valueToMergeInto.to < interval.to ? interval.value : valueToMergeInto.value,
                                });
                            }
                        }
                        newIntervals.forEach(period => addInterval(result, period));
                    } else {
                        const newIntervals: IInterval[] = [];
                        if (interval.from < valueToMergeInto.from) {
                            newIntervals.push({
                                from: interval.from,
                                to: subtractHour(valueToMergeInto.from),
                                value: interval.value,
                            }, {
                                from: valueToMergeInto.from,
                                to: Math.min(valueToMergeInto.to, interval.to),
                                value: interval.value,
                            });
                            if (interval.to !== valueToMergeInto.to) {
                                newIntervals.push({
                                    from: addHour(Math.min(valueToMergeInto.to, interval.to)),
                                    to: Math.max(valueToMergeInto.to, interval.to),
                                    value: valueToMergeInto.to < interval.to ? interval.value : 0,
                                });
                            }
                        } else {
                            if (interval.from !== valueToMergeInto.from) {
                                newIntervals.push({
                                    from: valueToMergeInto.from,
                                    to: subtractHour(interval.from),
                                    value: 0,
                                });
                            }
                            newIntervals.push({
                                from: interval.from,
                                to: Math.min(interval.to, valueToMergeInto.to),
                                value: interval.value,
                            });
                            if (interval.to !== valueToMergeInto.to) {
                                newIntervals.push({
                                    from: addHour(Math.min(valueToMergeInto.to, interval.to)),
                                    to: Math.max(valueToMergeInto.to, interval.to),
                                    value: valueToMergeInto.to < interval.to ? interval.value : 0,
                                });
                            }
                        }
                        const valuesToMergeIntoArray = result.splice(firstIntersectionIndex, count, ...newIntervals);
                        valuesToMergeIntoArray.forEach(period => addInterval(interval, period));
                    }
                }
            }
        }

Answer 1

Вы можете создавать записи для изменений суммы, которые происходят в отдельные моменты (во времени), так что вы фактически удвоите количество записей, которые есть у вашего ввода. Затем сортируйте по этому ключу. Сделайте ключи уникальными в этом отсортированном массиве, суммируя изменения количества, которые применяются к тому же ключу. Наконец, создайте вывод из этого массива.

function mergedIntervals(intervals) {
    let arr = [];
    // Store separate entries for "from" and for "to".
    for (let {from, to, amount} of data) {
        arr.push({ key: from, amountChange:  amount, countChange:  1});
        arr.push({ key: to+1, amountChange: -amount, countChange: -1});
    }
    // sort by key
    arr.sort((a, b) => a.key - b.key);
    // aggregate by key
    let last = {};
    let unique = [];
    let count = 0;
    let amount = 0;
    for (let {key, amountChange, countChange } of arr) {
        amount += amountChange
        count += countChange;
        if (key === last.key) {
            last.amount = amount;
            last.count = count;
        } else {
            unique.push(last = { key, amount, count });
        }
    }
    // generate result
    let result = [];
    last = null;
    for (let { key, amount, count } of unique) {
        if (last) last.to = key - 1;
        if (!count) {
            last = null;
        } else if (!last || last.amount !== amount) {
            result.push(last = { from: key, to: null, amount });
        }
    }
    return result;
}

// example run
let data = [ 
    {from: -5, to: 10, amount:  0}, // negative from
    {from: -4, to:  0, amount:  1}, // overlapping
    {from:  1, to:  2, amount:  2}, // adjacent to previous
    {from:  0, to:  6, amount: -5}, // negative amount
    // no coverage between 11 and 14
    {from: 15, to: 20, amount:  3}, // after gap
    {from: 18, to: 25, amount:  4}, // partly overlapping
];
console.log(mergedIntervals(data));

Answer 2

Этот подход является своего рода короткой версией tricot ' answer , которая полагается на отсортированный индекс, такой как ключи массивов в Javascript, и комбинированное значение sigle для определенного отметка времени.

Результат состоит из отсортированных записей объекта и проверяет, является ли последний объект или если сумма не равна нулю (в отличие от последней записи), новый объект помещается в результат набор.

function mergedIntervals(intervals) {
    let values = {},
        last,
        result = [],
        amount = 0;

    for (let { from, to, amount } of intervals) {
        values[from] = (values[from] || 0) + amount;
        values[to + 1] = (values[to] || 0) - amount;
    }

    for (let [k, v] of Object.entries(values)) {
        amount += v;
        if (last) {
            last.to = k - 1;
            if (amount === last.amount) continue;
        }
        result.push(last = { from: +k, to: null, amount });
    }
    result.pop();
    return result;
}

let data = [{ from: 1, to: 7, amount: 0 }, { from: 1, to: 2, amount: 1 }, { from: 3, to: 4, amount: 0 }, { from: 6, to: 7, amount: 1 }];

console.log(mergedIntervals(data));

.as-console-wrapper { max-height: 100% !important; top: 0; }