Merge arrays with overlapping values

Question

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 pairs of numbers. Think of these pairs of numbers as “start” and “end”. I want a function that takes numbers as an argument and a loop through its contents, and if the "start" number of the pair overlaps the "end" number of the previous pair, these arrays are combined into one. For instance:

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

Becomes as follows:

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

Actually, I already wrote a function for this, which works great, but feels a little awkward.

I am curious if any javascript master can blind me with an elegant solution =).

Answer 1

Create an empty array of results. Iterate over an array of ranges and either change the last element 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 the original array is sorted; if this is not always the case, sort it before merging:

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

Answer 2

I created a function that does what you want:

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

This function can be used as follows:

 var mergedNumbers = merge(numbers); 

Demo

Answer 3

As @Brett said, this might be better suited for Code Review (just include your current implementation). If you post there, put a link here here, and I will translate my answer.

---

Assuming your numbers array is already sorted correctly, this function should do what you want:

 function combine(numbers) { return numbers.reduce(function(combined, next) { if (!combined.length || combined[combined.length-1][1] < next[0]) combined.push(next); else { var prev = combined.pop(); combined.push([prev[0], Math.max(prev[1], next[1])]); } return combined; }, []); } var n = [[10, 20], [19, 40], [40, 60], [70, 80], [75, 76]]; var r = combine(n); document.write('<pre>' + JSON.stringify(r) + '</pre>'); 

This " reduce s" source array is for the new, using the following logic in the reduction function:

• If this is the first pass or the last element does not overlap the current element, push current element is in the combined array.
• Otherwise:
  • pop last element from the combined array.
  • push combination of the last element and the current element with the combined array.