Merge overlapping intervals

merge-overlapping-intervals.js

/* Merge overlapping intervals
 * 
 * Example:
 * [[1,4],[3,5],[2,4],[7,10]] -> [[1,5],[7,10]]
 */
function mergeIntervals(intervals) {
  // test if there are at least 2 intervals
  if(intervals.length <= 1)
    return intervals;

  var stack = [];
  var top   = null;

  // sort the intervals based on their start values
  intervals = intervals.sort();

  // push the 1st interval into the stack
  stack.push(intervals[0]);

  // start from the next interval and merge if needed
  for (var i = 1; i < intervals.length; i++) {
    // get the top element
    top = stack[stack.length - 1];

    // if the current interval doesn't overlap with the 
    // stack top element, push it to the stack
    if (top[1] < intervals[i][0]) {
      stack.push(intervals[i]);
    }
    // otherwise update the end value of the top element
    // if end of current interval is higher
    else if (top[1] < intervals[i][1])
    {
      top[1] = intervals[i][1];
      stack.pop();
      stack.push(top);
    }
  }

  return stack;
}

lines 35 and 36 can be removed I think

Fails with this input: [[1,3],[2,6],[8,10],[15,18]]
You need to use custom sort function, instead of using default.

Solution:

intervals = intervals.sort(function (startValue, endValue) {
    if (startValue[0] > endValue[0]) {
      return 1;
    }
    if (startValue[0] < endValue[0]) {
      return -1;
    }
    return 0;
  });

this sort function (standard) works well too

intervals.sort(function(a, b) {
return a[0] - b[0]
})

ES6 : intervals.sort((a, b) => a[0] - b[0])

You save my day, thanks

ES6 : intervals.sort((a, b) => a[0] - b[0])

Can go even further:

intervals.sort(([a0], [b0]) => a0 - b0)