JavaScript合并区间的算法

Question

举个例子:有如下三个区间:[     [1,100],     [50,200],     [300,400],     ...  //可以更多 ]现在需要一个算法来合并区间, 合并之后是:[     [1,200],     [300,400],     ... ]就是说重合的区间是需要合并的, 这样的算法该怎么写? 大神们给点思路吧

Answer 1

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))