Skip to content

JavaScript 合并区间的算法

举个例子: 有如下三个区间:

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

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

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

算法:

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

最后编辑时间:

Version 4.2 (core-1.3.4)