如何找到所有重叠的范围并将其划分为大块？ [英] How to find all overlapping ranges and partition them into chunks?

问题描述

我有一个范围数组，我希望能够找到所有重叠的范围：

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

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. 范围2与范围4重叠


2. 范围3与范围4重叠


3. 尽管范围2与范围3不重叠，因为它们都与范围4重叠。


4. 范围1和范围5仅相互重叠，并且因此他们将属于自己的小组

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在这里：

< a href = http://jsfiddle.net/jukufon7/2/ rel = nofollow> http://jsfiddle.net/jukufon7/2/

推荐答案

这是我的观点：

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:

这篇关于如何找到所有重叠的范围并将其划分为大块？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！