CODEWITHSUNDEEP
javascriptalgorithm
yuc
yuc

Reputation: 508

algorithm of counting Overlaps of ranges in javascript

input integer is always positive

input: [[1, 4], [3, 7], [6, 8], [10,15]]
output: [[1, 8], [10,15]]

input: [[3, 4], [1,3], [5, 9], [5, 12]]
output: [[1, 4], [5, 12]]

I read this stackoverflow, but wandering if there is a better way.

Upvotes: 1

Views: 143

Answers (4)

MBo
MBo

Reputation: 80187

For every start and end of range make a pair containing value and +1/-1 for start and end

Sort these pairs by value, using +-1 as secondary key in compare function: (x,+1) before (the same x,-1)

Make ActiveRanges=0, walk through pair list/array, adding +-1 to ActiveRanges.

When ActiveRanges becomes nonzero, big range begins.

When ActiveRanges becomes zero, big range finishes.

Upvotes: 2

osa
osa

Reputation: 79

If the array is of length 4 (as per your example) and everything is constant as you described it, here is a simple function you can use:

function reGroup(arr) {
    const x = [arr[0][0], arr[2][1]];
    return [x, arr[3]];
}

Upvotes: 0

Jeremy Thille
Jeremy Thille

Reputation: 26370

Here's what I came up with, usint the MathJS library to generate ranges :

let input = [[1, 4], [3, 7], [6, 8], [10,15]]

let workArray = input.map( arr => math.range(arr.join(":"), true )._data )
workArray = [].concat.apply([], workArray) // Concatenating all values
workArray = [...new Set(workArray)] // Deduplicating, sorting

let output = [],
	min = workArray[0],
	max = min

for( let i=0, l=workArray.length; i<l ; i++){
	if(max+1 != workArray[i+1]){
		output.push([min,max])
		min = workArray[i+1]
		max=min
	} else {
		max++	
	}
}

console.log(output) // [ [1,8] , [10,15] ]
<script src="https://cdnjs.cloudflare.com/ajax/libs/mathjs/3.13.1/math.min.js"></script>

Upvotes: 0

Nina Scholz
Nina Scholz

Reputation: 386604

You could sort the data ascending and then check the predecessor if it fits into the last range. If not append the actual array to the result set.

function groupRanges(array) {
    return array
        .sort(function (a, b) { return a[0]- b[0] || a[1]- b[1]; })
        .reduce(function (r, a) {
            var last = r[r.length - 1] || [];
            if (a[0] <= last[1]) {
                if (last[1] < a[1]) {
                    last[1] = a[1];
                }
                return r;
            }
            return r.concat([a]);
        }, []);
}

console.log(groupRanges([[1, 4], [3, 7], [6, 8], [10,15]]));
console.log(groupRanges([[3, 4], [1,3], [5, 9], [5, 12]]));
.as-console-wrapper { max-height: 100% !important; top: 0; }

Upvotes: 1

Related Questions