JavaScript合并区间的算法

问题描述

问 题

举个例子:

有如下三个区间:

[
    [1,100],
    [50,200],
    [300,400],
    ...  //可以更多
]

现在需要一个算法来合并区间, 合并之后是:

[
    [1,200],
    [300,400],
    ...
]

就是说重合的区间是需要合并的, 这样的算法该怎么写? 大神们给点思路吧

解决方案

function merge(intervals) {
    intervals.sort(function(a, b) {
        if (a[0] !== b[0])
            return a[0] - b[0];
        return a[1] - b[1];
    });
    var len = intervals.length,
        ans = [],
        start, end;

    for (var i = 0; i < len; i++) {
        var s = intervals[i][0],
            e = intervals[i][1];
        if (start === undefined)
            start = s, end = e;
        else if (s <= end)
            end = Math.max(e, end);
        else {
            var part = [start, end];
            ans.push(part);
            start = s;
            end = e;
        }
    }

    if (start !== undefined) {
        var part = [start, end];
        ans.push(part);
    }

    return ans;
};

var arr = [
    [1, 100],
    [50, 200],
    [300, 400]
]
console.log(merge(arr))

这篇关于JavaScript合并区间的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！