Skip to content

Instantly share code, notes, and snippets.

@aarongeorge
Created August 28, 2019 01:59
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save aarongeorge/6effb075250a7c823b996fce76ea3b9a to your computer and use it in GitHub Desktop.
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
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