Merge overlapping intervals (integer ranges)

merge_intervals.js

//
// Merge overlapping intervals
//

function merge_intervals(intervals){
  if (!intervals.length) return;
  // sort intervals based on start time
  intervals = intervals.sort(function(a, b){
    return a[0] - b[0]
  })
  // push the first interval onto the stack
  var stack = [intervals[0]]

  // start from next interval, merge if necessary
  for(var i=1; i< intervals.length; i++){
    // get the top of the stack
    var top = stack[stack.length-1]
    // if current interval is not overlapping with the stack top
    // push it to the stack
    if (top[1] < intervals[i][0]){
      stack.push( intervals[i] )
      continue;
    }
    // update end time of previous interval range
    // if the current interval end time is larger
    if (top[1] < intervals[i][1]){
      stack[stack.length-1][1] = intervals[i][1]
    }
  }
  return stack;
}


//
// tests
//

merge_intervals([[6,8],[1,9],[2,4],[4,7]])    // [[1,9]]
merge_intervals([[6,8],[1,3],[2,4],[4,7]])    // [[1,8]]
merge_intervals([[1,3],[7,9],[4,6],[10,13]])  // [[1,3], [4,6], [7,9], [10,13]]