Grouping an array of objects based on overlapping periods of time?

user_12209719 0
Viewed 42

I need to group objects based on overlapping periods.

const periods = [
  {start: 1, end: 4}, 
  {start: 1, end: 7}, 
  {start: 1, end: 4}, 
  {start: 5, end: 8},
  {start: 9, end: 12},
  {start: 9, end: 12}
]
 
const desiredOutput = [
 [{start: 1, end: 4}, {start: 5, end: 8}, {start: 9, end: 12}],
 [{start: 1, end: 7}, {start: 9, end: 12}]
 [{start: 1, end: 4}]
]

Basically if the periods overlap a new "row" is created, otherwise the object just gets pushed to the row that doesn't.

sorting arrays javascript
3 Answers

const periods = [
  {start: 1, end: 4}, 
  {start: 1, end: 7}, 
  {start: 1, end: 4}, 
  {start: 5, end: 8},
  {start: 9, end: 12},
  {start: 9, end: 12}
];

const sortedPeriods = periods.sort((a,b) => a.start-b.start);

const result = sortedPeriods.reduce((acc, p) => {
  for(i in acc) {
    if(acc.at(i).at(-1).end < p.start) {
      acc[i] = [...acc.at(i), p];
      return acc;
    }
  }
  return [...acc, [p]];
}, []);

console.log(result)

user_170703830

You can try this approach. Group perods base on addition start/end properties

const periods = [{ start: 1, end: 4 },{ start: 1, end: 7 },{ start: 1, end: 4 },{ start: 5, end: 8 },{ start: 9, end: 12 },{ start: 9, end: 12 }];

const areNotOverlap = (a, b) => a.end < b.start || a.start > b.end;

const groups = periods.reduce((acc, period) => {
  const { start, end } = period;
  const notOverlap = acc.find((accPeriod) => areNotOverlap(accPeriod, period));
  if (notOverlap) {
    notOverlap.periods.push(period);
    if (start < notOverlap.start) notOverlap.start = start;
    if (end > notOverlap.end) notOverlap.end = end;
    return acc;
  }
  
  acc.push({ start, end, periods: [period] });
  return acc;
}, []);

const result = groups.map(({ periods }) => periods);

console.log(result);
.as-console-wrapper { max-height: 100% !important; top: 0 }

user_877130

A small difference with nem0z's answer, but here's how I would do it:

const periods = [
  {start: 1, end: 4}, 
  {start: 1, end: 7}, 
  {start: 1, end: 4}, 
  {start: 5, end: 8},
  {start: 9, end: 12},
  {start: 9, end: 12}
]

const desiredOutput = [];

periods.forEach((period, index) => {
    const firstSetWithoutOverlap = desiredOutput.find(outputSet => 
      !outputSet.some(output => period.start === output.start)
    );
    if(firstSetWithoutOverlap === undefined) desiredOutput.push([ period ]);
    else firstSetWithoutOverlap.push(period);
}

Here's how it works. It first loops through every period. That does not need to be sorted per se. Then it looks in the desiredOutput array if it contains a list with an item where the start equals the start of the current period. If this is true, it looks at the next list, until it finds a list that does not contain a matching start value.

If all lists have matching start values, it creats a new array with the period as the first item. If it does find a list that does not have a matching start value, it pushes the current period to that list.

Considering we're talking about periods, I'm guessing you'd rather want to look into periods that don't overlap at all. For that, the check shouldn't look at start === start but rather if that start or end falls within another period.

const firstSetWithoutOverlap = desiredOutput.find(outputSet =>
  !outputSet.some(output => (period.start <= output.start && output.start <= period.end) || (period.start <= output.end && output.end <= period.end))

Finally, the sets made in desiredOutput may need to be sorted. For that, add this after the end of periods.forEach. The example below sorts both the desiredOutput as well as the sets within.

desiredOutput.forEach(outputSet =>
  outputSet.sort((firstOutput, secondOutput) => firstOutput.start - secondOutput.start);
);
desiredOutput.sort((firstSet, secondSet) =>
  firstSet[0].start - secondSet[0].start
)
user_197664930
Related