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 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 1

Expanding on accepted solution to provide more readability and a common use-case which is working with sets of integers where we want [[0,21],[22,42]] => [[0,42]]`:

const arr = [[21,21],[-21,1],[21,42],[5,10],[11,21]].sort((a, b) => a[0] - b[0]);
print(merge(arr));
print(merge(arr, true));

function merge(ranges, integers) { // range must be sorted by 1st element
  let prev = ranges[0];
  const result = [prev];

  for (let i = 1; i < ranges.length; i++) {
    const next = ranges[i];
    if (next[0] > prev[1] + (integers ? 1 : 0)) {
      result.push((prev = next));
      continue;
    }
    if (next[1] > prev[1]) prev[1] = next[1];
  }

  return result;
}

function print(value) {
  console.info(JSON.stringify(value))
}

Previous solutions are for closed intervals/ranges (where boundaries are included). This would be the approach for open intervals/ranges (boundaries not included):

const arr = [[21,21],[-21,1],[21,42],[5,10],[11,21]].filter(([a,b]) => a !== b).sort((a, b) => a[0] - b[0]); // 21 is not included
print(merge(arr));

function merge(ranges) { // range must be sorted by 1st element
  let prev = ranges[0];
  const result = [prev];

  for (let i = 1; i < ranges.length; i++) {
    const next = ranges[i];
    if (next[0] >= prev[1]) { // >= instead of >
      result.push((prev = next));
      continue;
    }
    if (next[1] > prev[1]) prev[1] = next[1];
  }

  return result;
}

function print(value) {
  console.info(JSON.stringify(value))
}

Answer 2

let arr = [
  [1, 3],
  [2, 6],
  [5, 10],
  [15, 18],
  [18, 6],
];

const mergeoverlapping = (arr) => {
  if (arr.length < 2) return intervals;
  arr.sort((a, b) => a[0] - b[0]);
  let top = 0;
  let down = arr.length - 1;
  let left = 0;
  let temp = [];
  let right = arr[0].length - 1;
  let result = [];
  while (top + 1 <= down) {
    if (arr[top][right] >= arr[top + 1][left]) {
      arr[top + 1][left] = arr[top][left];
      temp = [arr[top + 1][left], arr[top + 1][right]];
    } else {
      result.push(temp);
      temp = arr[top + 1];
    }
    top++;
  }
  result.push(temp);
  console.log(result);
};

console.log(mergeoverlapping(arr));

Answer 3

Simple concise JavaScript solution:

Algo

1. Sort the intervals by the start index in ascending order.
2. If the current interval overlap with the previous one, update the previous interval accordingly.
3. Otherwise, if the current start value > the previous end value), we put the interval in the result.

Implement code

var merge = (intervals) => {
  intervals.sort((a, b) => a[0] - b[0]);
  const merged = [intervals[0]];

  for (let i = 1; i < intervals.length; i++) {
    const [start, end] = intervals[i];
    let prev = merged[merged.length - 1];
    if (prev[1] >= start) {
      prev[1] = Math.max(prev[1], end);
    } else merged.push(intervals[i]);
  }
  return merged;
};

console.log(merge([[10, 20], [19, 40], [40, 60], [70, 80]]));

Answer 4

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

Answer 5

As @Brett said, this might be a better fit for Code Review (just be sure to include your current implementation). If you post there, put a reference to it here somewhere and I'll move my answer.

---

Assuming that 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 "reduces" the original array to the new one using the following logic in the reduce function:

1. If this is the first pass or the last item does not overlap the current item, push the current item on to the combined array.
2. Otherwise:
   1. pop the last item off the combined array.
   2. push the combination of the last item and the current item on to the combined array.

Answer 6

I created a function which 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 this way:

var mergedNumbers = merge(numbers);

DEMO