如何查找其他重疊號碼範圍之間的空閒號碼範圍

Question

我有n個陣列。每個數組都有m個元素。每個元素m由兩個屬性[數字]組成。

{ 
    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));