如何find其他重叠号码范围之间的免费号码范围
我有narrays。 每个数组有m个元素。 每个元素m由两个属性[数字]组成。
{ start: x end: y } 开始和结束号码，一起描述一个范围。 所以开始每一次都比结束小。 我试图find空闲的数字范围（再次与开始和结束），他们之间的所有arrays的范围元素。 另外结果是在一个范围内。
例如：
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} ];
这是我目前的工作解决scheme（ 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服务器上运行。 因为我们做了很多像这样的并发计算，我试图find一个资源高效的性能algorithm。 有没有更好的方法来实现呢？ 我的代码中有没有陷阱，导致性能问题？
这是你的简化版本。
// 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));