分割一组重叠范围的成一组非 - 重叠那些

Question

我有重叠范围的数组：

var ranges = [{ 
    "from": 0, 
    "to": 100 
}, { 
    "from": 50, 
    "to": 200 
}, { 
    "from": 0, 
    "to": 100 
}, { 
    "from": 70, 
    "to": 200 
}, { 
    "from": 90, 
    "to": 300 
}]; 

我需要将其转换成一组非 - 重叠的范围，也就是Ë：

var nonOverlapping = splitRanges(ranges); 

/* 
nonOverlapping = [{ 
    "from": 0, 
    "to": 49 
}, { 
    "from": 50, 
    "to": 69 
}, { 
    "from": 70, 
    "to": 89 
}, { 
    "from": 90, 
    "to": 100 
}, { 
    "from": 101, 
    "to": 200 
}, { 
    "from": 201, 
    "to": 300 
}] 
*/ 

我做了，做了这个功能（在JavaScript），但当然，你可以看到它的工作原理很慢，因为它使用了所谓的“天真办法”：

function splitRanges(ranges) { 
    var repeat, length, i, j; 
    var rangeA, rangeB, intersection; 
    do { 
     repeat = false; 
     length = ranges.length; 
     for (i = 0; i < length; i++) { 
      rangeA = ranges[i]; 
      for (j = i + 1; j < length; j++) { 
       rangeB = ranges[j]; 
       if (isIntersectingRanges(rangeA, rangeB)) { 
        repeat = true; 
        ranges.splice(i, 1); 
        intersection = splitRange(rangeA, rangeB); 
        while (intersection.length) { 
         ranges.push(intersection.shift()); 
        } 
       } 
       if (repeat) break; 
      } 
      if (repeat) break; 
     } 
    } while (repeat); 
} 

有人可以帮我重写这个，所以它的行为方式相同，而且比天真的方法更快吗？

编辑：

算法应该能够保持范围的轨道ID +正确处理范围从哪里==来：

var ranges = [{ 
    id: 1, 
    from: 0, 
    to: 100 
}, { 
    id: 2, 
    from: 30, 
    to: 30, 
}, { 
    id: 3, 
    from: 0, 
    to: 100 
}, { 
    id: 4, 
    from: 90, 
    to: 300 
}]; 

预期成果是：

[{ 
    "id": 3, 
    "from": 90, 
    "to": 100 
}, { 
    "id": 4, 
    "from": 90, 
    "to": 100 
}, { 
    "id": 4, 
    "from": 101, 
    "to": 300 
}, { 
    "id": 1, 
    "from": 0, 
    "to": 29 
}, { 
    "id": 1, 
    "from": 90, 
    "to": 100 
}, { 
    "id": 3, 
    "from": 0, 
    "to": 29 
}, { 
    "id": 1, 
    "from": 30, 
    "to": 30 
}, { 
    "id": 1, 
    "from": 31, 
    "to": 89 
}, { 
    "id": 2, 
    "from": 30, 
    "to": 30 
}, { 
    "id": 3, 
    "from": 30, 
    "to": 30 
}, { 
    "id": 3, 
    "from": 31, 
    "to": 89 
}] 

Answer 1

这会产生您指定输入的必要结果：

function splitRanges (intervals) { 'use strict'; 
    // Create arrays of the from and to values, do not record duplicate values 
    for (var to = [], from = [], n, i = intervals.length; i--;) { 
    if (to.indexOf (n = intervals[i].to) < 0) 
     to.push (n); 
    if (from.indexOf (n = intervals[i].from) < 0) 
     from.push (n); 
    } 

    // Sort both arrays 
    to.sort (function (a, b) { return a-b; }); 
    from.sort (function (a, b) { return a-b; }); 

    // Create new intervals array 
    intervals = []; 
    while (to.length) 
    intervals.push ({ 
     from: from.shift(), 
     to: from.length == 0 ? (from.push ((n = to.shift()) + 1), n) : 
      from[0] > to[0] ? from[1] - 1 : from[0] - 1 
    }); 

    return intervals; 
} 

当相同的数字出现在a和a之间时，就会产生一个“虚假的”零范围。不知道这种情况是否会在您的数据中发生，或者额外的范围是否有问题