合并具有重叠值的数组

Question

我正在使用Node.js. (...和underscore.js)

考虑这个数据结构

var numbers = [
  [10, 20]
  [30, 40]
  [40, 50]
  [45, 70]
  ... //Possibly more arrays (always contains two numbers)
]

numbers包含始终包含数字对的数组.将这些数字对视为"开始"和"结束".我想要一个numbers作为参数的函数,并循环其内容,如果一对的"开始"数字与前一对的"结束"数重叠,则这些数组合并为一个.例如:

var numbers = [
  [10, 20]
  [19, 40]
  [40, 60]
  [70, 80]
]

变成这样:

var numbers = [
  [10, 60] // First, second and third array is merged because of overlapping . 
  [70, 80]
]

实际上,我已经为此编写了一个功能正常的功能,但感觉有点笨重.

我很好奇,如果一些javascript向导可以用超级优雅的解决方案炫耀我=).

Answer 1

创建一个空的"结果"数组.循环遍历范围数组,并更改结果的最后一项或向其添加当前范围.

function merge(ranges) {
    var result = [], last;

    ranges.forEach(function (r) {
        if (!last || r[0] > last[1])
            result.push(last = r);
        else if (r[1] > last[1])
            last[1] = r[1];
    });

    return result;
}

r = [[10, 20], [19, 40], [40, 60], [70, 80]];
document.write(JSON.stringify(merge(r)));

这假设源数组已排序,如果情况并非总是如此,请在合并之前对其进行排序:

ranges.sort(function(a, b) { return a[0]-b[0] || a[1]-b[1] });

Answer 2

我创建了一个功能,它可以做你想要的:

function merge(arr) {
    // copy and sort the array
    var result = arr.slice().sort(function(a, b) {
            return a[0] > b[0];
        }),
        i = 0;

    while(i < result.length - 1) {
        var current = result[i],
            next = result[i+1];

        // check if there is an overlapping
        if(current[1] >= next[0]) {
            current[1] = Math.max(current[1], next[1]);
            // remove next
            result.splice(i+1, 1);
        } else {
            // move to next
            i++;
        }
    }
    return result;
};

这个函数可以这样使用:

var mergedNumbers = merge(numbers);

DEMO