Group all overlapping intervals.

group-intervals.js

// Group all overlaping intervals
// * * * * * * *  
// This is an approach to a problem the engineers at Google Calandar/ Outlook probably faced. 
// You have events that may overlap and you want to display them in such a way that 
// they don't overlap with each other. One approach is to distribute them into columns. 
// Each column has events that don't overlap with each other.
 
// Cost: O(n*log n) if the interval aren't sorted by the starting time, 
//   O(n) otherwise.
// Sample run: groupOverlapingIntervals([ [2, 5], [5, 6],[3, 4] ])
// Output: [ [ [2, 5], [3, 4], [5, 6] ] ]
function groupOverlapingIntervals(intervals) {
  intervals.sort(function(a, b) {
    return  a[0] - b[0];
  });
 
  var groups = [[intervals[0]]];
  var j = 0;
  var end = intervals[0][1];
 
  for (var i = 1; i < intervals.length; i++) {
    if (intervals[i][0] <= end) {
      if (intervals[i][1] > end) {
        end = intervals[i][1];
      }
      groups[j].push(intervals[i]);
    } else {
      groups.push([intervals[i]]);
      j++;
      end = intervals[i][1];
    }
  }
  return groups;
}
 
// Group all non overlaping intervals
// Cost: O(n*log n) if the interval aren't sorted by the starting time, 
//   O(n) otherwise.
function groupNonOverlapingIntervals(intervals) {
  intervals.sort(function(a, b) {
    return  a[0] - b[0];
  });
 
  var groups = [[intervals[0]]];
  var j = 0;
  var end = intervals[0][1];
 
  for (var i = 1; i < intervals.length; i++) {
    if (intervals[i][0] > end) {
      if (intervals[i][1] > end) {
        end = intervals[i][1];
      }
      groups[j].push(intervals[i]);
    } else {
      groups.push([intervals[i]]);
      j++;
      end = intervals[i][1];
    }
  }
  return groups;
}