合并重叠区间的快速算法

Question

我正在尝试编写一个足够快的算法来合并区间与值。

例如有3个区间（包括from和to）：

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

结果：

{from:1, to: 1, amount: 1}
{from:2, to: 3, amount: 2}
{from:4, to: 4, amount: 1}
{from:5, to: 6, amount: 2}
{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's 的一种简短版本，它依赖于Javascript中数组键的排序索引和特定时间戳的组合单值。

结果由对象的排序条目组成，并检查是否是最后一个对象或者数量是否不为零（与最后一个条目相反）将新对象推送到结果集。

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; }

合并重叠区间的快速算法

fast algorithm for merging overlapping intervals

javascript

algorithm

intervals