Created
August 28, 2019 01:59
-
-
Save aarongeorge/6effb075250a7c823b996fce76ea3b9a to your computer and use it in GitHub Desktop.
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