Given an array of ranges, group overlapping ranges in an array and return an array of the groups
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
const ranges = [ | |
{ | |
'start': 6, | |
'end': 8 | |
}, | |
{ | |
'start': 3, | |
'end': 6 | |
}, | |
{ | |
'start': 9, | |
'end': 10 | |
}, | |
{ | |
'start': 0, | |
'end': 4 | |
}, | |
{ | |
'start': 8, | |
'end': 10 | |
}, | |
{ | |
'start': 5, | |
'end': 6 | |
}, | |
{ | |
'start': 7, | |
'end': 10 | |
} | |
]; | |
const sortArrayByProp = (arr, prop, direction = 'asc') => { | |
return [...arr].sort((a,b) => { | |
if (a[prop] < b[prop]) { | |
return direction === 'asc' ? -1 : 1; | |
} | |
if (a[prop] > b[prop]) { | |
return direction === 'asc' ? 1 : -1; | |
} | |
return 0; | |
}); | |
}; | |
const getLargestPropInArray = (arr, prop) => { | |
return arr.length === 0 ? false : sortArrayByProp(arr, prop, 'desc')[0][prop]; | |
}; | |
const groupOverlappingRanges = (ranges, startProp = 'start', endProp = 'end') => { | |
const groupedRanges = []; | |
let groupIndex = 0; | |
// Sort `ranges` by `startProp` | |
ranges = sortArrayByProp(ranges, startProp); | |
// Add the first item in `ranges` to the first group | |
groupedRanges[groupIndex] = [ranges[0]]; | |
for (let i = 1, l = ranges.length; i < l; i++) { | |
// Check that the current range `startProp` is bigger or the same as the previous, and it's less than the largest `endProp` in the current `groupedRanges[groupIndex]` | |
if ((ranges[i][startProp] >= ranges[i - 1][startProp]) && (ranges[i][startProp] < getLargestPropInArray(groupedRanges[groupIndex], endProp))) { | |
groupedRanges[groupIndex].push(ranges[i]); | |
} | |
// Start a new group | |
else { | |
groupIndex++; | |
groupedRanges[groupIndex] = [ranges[i]]; | |
} | |
} | |
return groupedRanges; | |
}; | |
groupOverlappingRanges(ranges); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment