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