Consolidating overlapping sets from an array of sets
I have an array with each entry containing a minimum and a maximum value for a bunch of sets such as the one below:
Array
(
[0] => Array
(
[0] => 1200
[1] => 2400
)
[1] => Array
(
[0] => 1400
[1] => 3800
)
[2] => Array
(
[0] => 2700
[1] => 4200
)
[3] => Array
(
[0] => 5900
[1] => 6400
)
)
For each index, the 0 index is the minimum value and the 1 index is the maximum value for that particular set. I need to create a javascript or php function to consolidate this array so that the sets that overlap are turned into one. So, the above array would turn into the following:
Array
(
[0] => Array
(
[0] => 1200
[1] => 4200
)
[1] => Array
(
[0] => 5900
[1] => 6400
开发者_StackOverflow社区)
)
As you can see, from the first array indicies 0, 1, and 2 were consolidated into index 0 for the second array. Index 3 from the first array did not overlap with any other set so that became index 1 in the second array.
The original array itself will contain around 70 to 80 sets and the min and max values can get as high as 9999999999 so iterating through a number line in a n, n+1, n+2 manner is not feasible.
Any ideas?
UPDATE + SOLUTION
As stated in the comment below, this is indeed a repost (didn't see the other post). The link for the solution is at the link below:
Merging overlapping ranges in PHP arrays?
Assuming the sets are ordered by lower bound, as in the example, how about something like this?
var newIndex = 0;
var newSetArray[newIndex][0] = setArray[0][0];
for (i = 1; i < setArray.length; i++) {
if (setArray[i-1][1] < setArray[i][0]) {
newSetArray[newIndex][1] = setArray[i-1][1];
newSetArray[++newIndex][0] = setArray[i][0];
}
}
newSetArray[newIndex][1] = setArray[setArray.length-1][1];
The syntax might need some tweaks, but I think this should work.
精彩评论