拆分一组日期范围项目，每个项目都有一个开始和结束时间戳，这些时间戳可以相互重叠成单独的非重叠范围数组？

Question

假设我有一个如下所示的数组，如果时间重叠，最好的方法是将它们分成单独的数组？我正在使用 moment 但有点不确定如何解决这个问题。

我知道我必须先对数组进行排序。

数据：

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' },
];

预计：

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',
    },
  ],
];

Answer 1

将其分解成更小的块并解决每个问题。如果您最终遇到多个重叠 class，我不确定您的计划是什么。这段代码只是 returns 一个包含两个元素的数组：独特的 classes 和重叠的 classes，它不会为每个违规的 class.[= 添加新元素。 11=]

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));

Answer 2

通用方法必须通过任何给定的原始 timetable（源数组）递归地工作，以便 detect/generate 尽可能多的时间 tables 每个特征只是不重叠时间范围项目。

只要在已处理的数组中仍然找到重叠的时间范围项，递归实现就会重复调用自身。

部分方法是，这样的自递归函数确实创建了经过时间的浅表副本table，并且在最初被调用时确实对其进行了一次精确排序。

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; }

拆分一组日期范围项目，每个项目都有一个开始和结束时间戳，这些时间戳可以相互重叠成单独的非重叠范围数组？

Split an array of date range items each with a start and an end timestamp which can overlap each other into separate arrays of non overlapping ranges?

javascript

arrays

sorting

datetime

slice