Merge arrays with overlapping values

Im using Node.js. (…and underscore.js)

Consider this data structure

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

numbers contain arrays that always contain number pairs. Think of these number pairs as “start” and “end”. I want a function that takes numbers as argument, and loop trough its content, and if the “start” number of a pair overlap the “end” number of previous pair, these arrays is merged into one. For example this:

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

Becomes this:

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

Actually, I already have written a function for this that works fine, but feels a bit clunky.

I’m curious if some javascript wizard can dazzle me with a super elegant solution =).

Answer

Create an empty “result” array. Loop over the ranges array and either change the last item of the result or add the current range to it.

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

This assumes that the source array is sorted, if it’s not always the case, sort it before merging:

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