开发者

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.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜