Split an array of date range items each with a start and an end timestamp which can overlap each oth-CodePudding

Say I have an array such as below, what would the best method be to separate these into individual arrays if the times overlap? I'm using moment but am a bit unsure of how to tackle this.

I know I have to sort the array initially.

data:

const timetable = [
  { class: 'one', start: '2021-11-16T09:00:00', end: '2021-11-16T10:00:00' },
  { class: 'two', start: '2021-11-16T010:00:00', end: '2021-11-16T11:00:00' },
  { class: 'three', start: '2021-11-16T09:00:00', end: '2021-11-16T10:00:00' },
];

expected:

const timetable = [
  [
    { class: 'one', start: '2021-11-16T09:00:00', end: '2021-11-16T10:00:00' },
    { class: 'two', start: '2021-11-16T010:00:00', end: '2021-11-16T11:00:00' },
  ],
  [
    {
      class: 'three',
      start: '2021-11-16T09:00:00',
      end: '2021-11-16T10:00:00',
    },
  ],
];

CodePudding user response：

A generic approach has to work itself recursively through any given original timetable (source array) in order to detect/generate as much time tables which each feature just non-overlapping time range items.

A recursive implementation would call itself repeatedly as long as there are, within a processed array, still overlapping time range items found.

Part of the approach is, that such a self recursive function does create a shallow copy of the passed time table and also does sort it exactly once, at the time of being called initially.

function parseTime(value) {
  return new Date(value).getTime();
}
function getParsedTimeRangeFromItem({ start, end }) {
  return {
    start: parseTime(start),
    end: parseTime(end),
  }
}

function orderByTimeRangeAscending(a, b) {
  const { start: aStart, end: aEnd } = getParsedTimeRangeFromItem(a);
  const { start: bStart, end: bEnd } = getParsedTimeRangeFromItem(b);

  return (aStart - bStart) || (aEnd - bEnd);
}

function createTimetablesOfNonOverlappingTimeRanges(timetable, result) {
  // at initial call time only ...
  if (!Array.isArray(result)) {
    // ... create the result array ...
    result = [];
    // ... and also a shallow and sorted copy
    //     of the initially passed `timetable`.
    timetable = [...timetable].sort(orderByTimeRangeAscending);
  }
  const rejected = [];

  let idx = -1;
  let item, nextItem;

  while (
    (item = timetable[  idx]) &&
    (nextItem = timetable[idx   1])
  ) {
    // detect `nextItem` as overlapping time range item ...
    if (parseTime(item.end) > parseTime(nextItem.start)) {

      // ... and reject it from the `timetable` reference.
      rejected.push(timetable.splice((idx   1), 1)[0])
      --idx;
    }
  }
  // add the sanitized but mutated `timetable` to `result`.
  result.push(timetable);

  // in case of any rejected time range item trigger self recursion.
  if (rejected.length >= 1) {
    result =
      createTimetablesOfNonOverlappingTimeRanges(rejected, result);
  }
  return result;
}


const timetable = [
  { class: 'one', start: '2021-11-16T09:00:00', end: '2021-11-16T10:00:00' },
  { class: 'two', start: '2021-11-16T10:00:00', end: '2021-11-16T11:00:00' },
  { class: 'three', start: '2021-11-16T09:00:00', end: '2021-11-16T10:00:00' },
  { class: 'four', start: '2021-11-16T09:00:00', end: '2021-11-16T10:00:00' },
  { class: 'five', start: '2021-11-16T10:00:00', end: '2021-11-16T11:00:00' },
  { class: 'six', start: '2021-11-16T09:00:00', end: '2021-11-16T10:00:00' },
];

console.log(
  '[...timetable].sort(orderByTimeRangeAscending) ...',
  [...timetable]
    .sort(orderByTimeRangeAscending)
);
console.log(
  'createTimetablesOfNonOverlappingTimeRanges(timetable) ...',
  createTimetablesOfNonOverlappingTimeRanges(timetable)
);
console.log('un-mutated original source array ...', { timetable });

.as-console-wrapper { min-height: 100%!important; top: 0; }

CodePudding user response：

Break it down into smaller chunks and tackle each problem. I'm not sure what your plan is if you end up with multiple overlapping classes. This code just returns an array with two elements: unique classes and overlapping classes, it doesn't keep adding on new elements for each offending class.

const timetable = [
  { class: "one", start: "2021-11-16T09:00:00", end: "2021-11-16T10:00:00" },
  { class: "two", start: "2021-11-16T10:00:00", end: "2021-11-16T11:00:00" },
  { class: "three", start: "2021-11-16T09:00:00", end: "2021-11-16T10:00:00" },
];

// get an object, return a new object with the times as
// timestamps, rather than time strings
// (you don't need Moment.JS, JavaScript has .getTime())
const parseTimes = el => {
  const hour = {...el};
  hour.start = new Date(el.start).getTime();
  hour.end = new Date(el.end).getTime();
  return hour;
};

// given two objects, see if one is fully before or after
// another. If not, they overlap.
const overlaps = (a, b) => {
  if (a.start <= b.start && a.end <= b.start) return false;
  if (a.end >= b.end && a.start >= b.end) return false;
  return true;
};

// given an array and a starting place, figure out if any
// of the objects overlap any of the previous objects
const overlapsPrevious = (arr, idx) => {
  const a = parseTimes(arr[idx]);
  for (let ix = 0; ix <= idx; ix  ) {
    const b = parseTimes(arr[ix]);
    if (a.class !== b.class && overlaps(a, b)) return true;
  }
  return false;
};

// given an array, return a new array with non-overlaping
// objects and objects that overlap
const split = (arr) => {
  const unique = [];
  const overlap = [];
  for(let ix = 0; ix < arr.length; ix  ) {
    if(overlapsPrevious(arr, ix)) overlap.push(arr[ix]);
    else unique.push(arr[ix]);
  }
  return [unique, overlap];
}

// display the result
console.log(split(timetable));