JavaScript合并区间的算法

Question

举个例子:

有如下三个区间:

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

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

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

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

Answer 1

function merge(intervals) {&nbsp; &nbsp; intervals.sort(function(a, b) {&nbsp; &nbsp; &nbsp; &nbsp; if (a[0] !== b[0])&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return a[0] - b[0];&nbsp; &nbsp; &nbsp; &nbsp; return a[1] - b[1];&nbsp; &nbsp; });&nbsp; &nbsp; var len = intervals.length,&nbsp; &nbsp; &nbsp; &nbsp; ans = [],&nbsp; &nbsp; &nbsp; &nbsp; start, end;&nbsp; &nbsp; for (var i = 0; i < len; i++) {&nbsp; &nbsp; &nbsp; &nbsp; var s = intervals[i][0],&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; e = intervals[i][1];&nbsp; &nbsp; &nbsp; &nbsp; if (start === undefined)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; start = s, end = e;&nbsp; &nbsp; &nbsp; &nbsp; else if (s <= end)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; end = Math.max(e, end);&nbsp; &nbsp; &nbsp; &nbsp; else {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; var part = [start, end];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ans.push(part);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; start = s;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; end = e;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; if (start !== undefined) {&nbsp; &nbsp; &nbsp; &nbsp; var part = [start, end];&nbsp; &nbsp; &nbsp; &nbsp; ans.push(part);&nbsp; &nbsp; }&nbsp; &nbsp; return ans;};var arr = [&nbsp; &nbsp; [1, 100],&nbsp; &nbsp; [50, 200],&nbsp; &nbsp; [300, 400]]console.log(merge(arr))