如何在其他重叠的数字范围之间找到可用的数字范围
How to find free number ranges between other overlapping number ranges
我有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服务器上运行。因为我们做了很多这样的并发计算,所以我试图找到一种资源高效且性能良好的算法。有更好的方法来实现这一点吗?我的代码中是否存在导致性能问题的陷阱?
这里有一个简化版本。
// 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));
相关文章:
- 如何在JavaScript中使用此函数对范围内的所有数字求和
- JS:从数组中查找特定范围内的最低/最高数字
- 试图检查表单中的值是否为一个设定范围内的数字
- 需要将变量设置为特定的数字范围
- 不断提示用户一个数字,直到它落入某个范围
- 使用javascript将数字缩放为一个范围
- 用于验证数字范围的正则表达式
- Regex-用只匹配数字的量词匹配字符范围
- 检查数字是否在特定范围内
- 正则表达式用于验证两个范围之间的数字
- 从显示为文本的范围中返回最小和最大数字
- 检查值是否在某个数字的范围内
- jQuery 验证 - 带逗号的数字进入特定范围
- 数字在范围内的条件 - Titanium/Javascript
- Javascript/Jquery:使用数字范围验证输入
- 创建使用用户输入的数字范围生成的随机数.(JavaScript)
- 如何检查对象中的所有数字是否都在一定范围内
- 需要Javascript数学表达式或公式来将数字范围放在组中
- Javascript - 在一定范围内生成随机数,不包括某些数字
- Javascript / jQuery - 将一个数字范围映射到另一个数字范围