How to find all overlapping ranges and partition them into chunks?

Question

I have an array of ranges and I want to be able to find all the overlapping ranges:

For example:

var examples = [
    // Group 1
    {start: 9, end: 10.50},       // Range 1
    {start: 10, end: 10.50},      // Range 5

    // Group 2
    {start: 11, end: 13},         // Range 2
    {start: 13.5, end: 14.5},     // Range 3
    {start: 11.5, end: 14}        // Range 4
]

1. Range 2 overlaps with Range 4
2. Range 3 overlaps with Range 4
3. Although Range 2 does not overlap with Range 3, because they both overlap with Range 4. They will be put into the same group
4. Range 1 and Range 5 only overlap with each other and so they will be in their own group

JSFiddle here:

http://jsfiddle.net/jukufon7/2/

Answer 1

Here's my take:

jsfiddle

var examples = [
    {start: 17, end: 20},
    {start: 9, end: 10.50},
    {start: 15, end: 17},
    {start: 11, end: 12},
    {start: 18, end: 19.5},
    {start: 19.5, end: 22},
    {start: 11.5, end: 12.5},
    {start: 11.5, end: 13},
    {start: 17.5, end: 18.5},
    {start: 19, end: 19.5},
    {start: 22, end: 25}
]

function partitionIntoOverlappingRanges(array) {
  array.sort(function (a,b) {
    if (a.start < b.start)
      return -1;
    if (a.start > b.start)
      return 1;
    return 0;
  });
  var getMaxEnd = function(array) {
    if (array.length==0) return false;
    array.sort(function (a,b) {
      if (a.end < b.end)
        return 1;
      if (a.end > b.end)
        return -1;
      return 0;
    });
    return array[0].end;    
  };
  var rarray=[];
  var g=0;
  rarray[g]=[array[0]];

  for (var i=1,l=array.length;i<l;i++) {
    if ( (array[i].start>=array[i-1].start)
         &&
         (array[i].start<getMaxEnd(rarray[g]))
    ) {    
      rarray[g].push(array[i]);
    } else {
      g++;   
      rarray[g]=[array[i]];
    }
  }
  return rarray;
} // end partitionIntoOverlappingRanges

Results from examples above:

Answer 2

Here's a simple scanning algorithm. It executes in O(n log n) because of the necessity to sort the ranges.

The basic idea is to just scan from left to right looking for both start and end points (which requires a sorted list of each of those). While scanning, keep track of the number of active ranges (that is, ranges whose start point has been encountered and whose endpoint has not yet been encountered). Every time you hit a start-point, the range needs to be added to the current group. The range count is maintained by incrementing it at each start point and decrementing it at each end point. Every time the count returns to 0, a complete group has been found.

If you want to compute the simplified set of ranges instead of the groups, you can simplify. Instead of keeping a set of ranges in a group, the start point of the current composed group is set when the active range count increments from 0 to 1, and the end point is set when the active range count decrements from 1 to 0. In this case, you only need a sorted list of start points and a sorted list of end points (in the algorithm as presented, the sorted start points are found by sorting the ranges themselves by start point. The group is needed so that the range can be added to the accumulated group.)

1. Sort the ranges by their start values.

2. Make a list of the end values, and sort it (it's not necessary to know which range belongs to an endpoint). Call this end_values.

3. Initialize current_group to an empty set, and active_range_count to 0. Initialize current_range and current_end to 0.

4. Loop until done:

   1. If current_range is a valid index into ranges and ranges[current_range].start is less than end_values[current_end]:

      • Add ranges[current_range] to current_group, increment current_range and increment active_range_count.
      • Loop.

   2. Otherwise, if current_end is a valid index into end_values:

      • Decrement active_range_count and increment current_end.
      • If active_range_count is 0, then current_group is complete; save it, and reinitialize current_group to an empty set.
      • Loop.

   3. Otherwise, done.

Here are both versions in javascript:

/* Partition an array of ranges into non-overlapping groups */
/* Side-effect: sorts the array */
function partition(ranges) {
  var end_values = ranges.map(function(r){return r.end}).sort(function(a, b){return a - b})
  ranges.sort(function(a, b){return a.start - b.start})
  var i = 0, j = 0, n = ranges.length, active = 0
  var groups = [], cur = []
  while (1) {
    if (i < n && ranges[i].start < end_values[j]) {
      cur.push(ranges[i++])
      ++active
    } else if (j < n) {
      ++j  
      if (--active == 0) {
        groups.push(cur)
        cur = [] 
      }    
    } else break   
  }
  return groups
}

/* Given a array of possibly overlapping ranges, produces
 * an array of non-overlapping ranges covering the same
 * values.
 */
function compose_ranges(ranges) {
  var starts = ranges.map(function(r){return r.start}).sort(function(a, b){return a - b})
  var ends = ranges.map(function(r){return r.end}).sort(function(a, b){return a - b})
  var i = 0, j = 0, n = ranges.length, active = 0
  var combined = []
  while (1) {
    if (i < n && starts[i] < ends[j]) {
      if (active++ == 0) combined.push({start: starts[i]})
      ++i
    } else if (j < n) {
      if (--active == 0) combined[combined.length - 1].end = ends[j]
      ++j
    } else break;
  } 
  return combined
}