如何找到所有重叠的范围并将其划分为大块? [英] How to find all overlapping ranges and partition them into chunks?
本文介绍了如何找到所有重叠的范围并将其划分为大块?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
我有一个范围数组,我希望能够找到所有重叠的范围:
I have an array of ranges and I want to be able to find all the overlapping ranges:
var examples = [
// Group 1
{start: 9, end: 10.50}, // Range 1
{start: 10, end: 10.50}, // Range 5
// Group 2
{start: 11, end: 13}, // Range 2
{start: 13.5, end: 14.5}, // Range 3
{start: 11.5, end: 14} // Range 4
]
- 范围2与范围4重叠
- 范围3与范围4重叠
- 尽管范围2与范围3不重叠,因为它们都与范围4重叠。
- 范围1和范围5仅相互重叠,并且因此他们将属于自己的小组
- Range 2 overlaps with Range 4
- Range 3 overlaps with Range 4
- Although Range 2 does not overlap with Range 3, because they both overlap with Range 4. They will be put into the same group
- Range 1 and Range 5 only overlap with each other and so they will be in their own group
JSFiddle在这里:
< a href = http://jsfiddle.net/jukufon7/2/ rel = nofollow> http://jsfiddle.net/jukufon7/2/
推荐答案
这是我的观点:
var examples = [
{start: 17, end: 20},
{start: 9, end: 10.50},
{start: 15, end: 17},
{start: 11, end: 12},
{start: 18, end: 19.5},
{start: 19.5, end: 22},
{start: 11.5, end: 12.5},
{start: 11.5, end: 13},
{start: 17.5, end: 18.5},
{start: 19, end: 19.5},
{start: 22, end: 25}
]
function partitionIntoOverlappingRanges(array) {
array.sort(function (a,b) {
if (a.start < b.start)
return -1;
if (a.start > b.start)
return 1;
return 0;
});
var getMaxEnd = function(array) {
if (array.length==0) return false;
array.sort(function (a,b) {
if (a.end < b.end)
return 1;
if (a.end > b.end)
return -1;
return 0;
});
return array[0].end;
};
var rarray=[];
var g=0;
rarray[g]=[array[0]];
for (var i=1,l=array.length;i<l;i++) {
if ( (array[i].start>=array[i-1].start)
&&
(array[i].start<getMaxEnd(rarray[g]))
) {
rarray[g].push(array[i]);
} else {
g++;
rarray[g]=[array[i]];
}
}
return rarray;
} // end partitionIntoOverlappingRanges
示例的结果
Results from examples
above:
这篇关于如何找到所有重叠的范围并将其划分为大块?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文