javascript - 如何找到其他重叠号码范围之间的空闲号码范围

Question

我有 n 个数组。每个数组有 m 个元素。每个元素 m 由两个属性 [numbers] 组成。

{
  start: x
  end: y
}

起始编号和结束编号共同描述了一个范围。所以开始每次都小于结束。我尝试找到空闲数字范围(同样是开始和结束)，它们位于所有数组中的范围元素之间。另外，结果在一个范围内。

例如:

var boundary = {
    start: 0,
    end: 600
};

// for example i use two arrays with ranges, but in reality they are n (>= 1)
var numbersRanges1 = [
    {start: 100, end: 120},
    {start: 180, end: 200},
    {start: 400, end: 500}
];

var numbersRanges2 = [
    {start: 10, end: 80},
    {start: 150, end: 220},
    {start: 480, end: 500}
];

// result should look like
var expected = [
    {start: 0, end: 10},
    {start: 80, end: 100},
    {start: 120, end: 150},
    {start: 220, end: 400},
    {start: 500, end: 600}
];

这是我目前的工作解决方案(JS Bin)

var boundary = {
    start: 0,
    end: 600
};

// for example i use two arrays with ranges, but in reality they are n (>= 1)
var numbersRanges1 = [
    {start: 100, end: 120},
    {start: 180, end: 200},
    {start: 400, end: 500}
];

var numbersRanges2 = [
    {start: 10, end: 80},
    {start: 150, end: 220},
    {start: 480, end: 500}
];

// result should look like
var expected = [
    {start: 0, end: 10},
    {start: 80, end: 100},
    {start: 120, end: 150},
    {start: 220, end: 400},
    {start: 500, end: 600}
];

// merge arrays
var mergedRanges = numbersRanges1.concat(numbersRanges2);


// sort by start
function sortByStart(a, b){
    return a.start - b.start;
}

mergedRanges = mergedRanges.sort(sortByStart);

// group overlapping ranges
for(var i = 1; i < mergedRanges.length; i++){
    var range1 = mergedRanges[i-1];
    var range2 = mergedRanges[i];

    if((range1.start <= range2.end) && (range1.end >= range2.start)){
        range2.start = Math.min(range1.start, range2.start);
        range2.end = Math.max(range1.end, range2.end);
        mergedRanges.splice(i-1, 1);
    }
}

// go throw merged ranges and save ranges between in addition array
var freeRanges = [];

if(mergedRanges[0].start > boundary.start){
    freeRanges.push({
        start: boundary.start,
        end: mergedRanges[0].start
    });
}

for(var i = 1, mergedLen = mergedRanges.length; i <  mergedLen; i++){
    freeRanges.push({
        start: mergedRanges[i-1].end,
        end: mergedRanges[i].start
    });
}

if(mergedRanges[mergedLen-1].end < boundary.end){
    freeRanges.push({
        start: mergedRanges[mergedLen-1].end,
        end: boundary.end
    });
}

console.log(freeRanges);
console.log(expected);

脚本在 node.js 服务器上运行。因为我们做了很多像这样的并发计算，所以我试图为此找到一种资源高效和高性能的算法。有没有更好的方法来实现这一目标？我的代码中是否存在导致性能问题的缺陷？

Answer 1

这是为您准备的简化版本。

// for example i use two arrays with ranges, but in reality they are n (>= 1)
var numbersRanges1 = [
    {start: 100, end: 120},
    {start: 180, end: 200},
    {start: 400, end: 500}
];

var numbersRanges2 = [
    {start: 10, end: 80},
    {start: 150, end: 220},
    {start: 480, end: 500}
];

var boundary = {
    start: 0,
    end: 600
};

// merge arrays
var mergedRanges = numbersRanges1.concat(numbersRanges2);

// sort by start
function sortByStart(a, b){
    return a.start - b.start;
}

mergedRanges = mergedRanges.sort(sortByStart);

// go throw merged ranges and save ranges between in addition array
var freeRanges = [];

var start=0;
mergedRanges.forEach(function(one) {
  if(one.start<start) return;
  freeRanges.push({start:start,end:one.start});
  start=one.end;
});

if(start<boundary.end) {
  freeRanges.push({start:start,end:boundary.end});
}

console.log(JSON.stringify(freeRanges,null,2));