algorithm - 改进慢速算法的反馈

Question

我在为以下问题创建高性能函数时遇到了问题。我正在构建一个时间表，我需要将列中的项目数组分开，以便没有列有 2 个项目在其开始/结束时间范围内共享一个小时。

我当前的解决方案有效，但特别是在所有项目都具有相同小时范围的最坏情况下会进行大量浪费的计算，并且它会为每个项目创建一个新列。

function getItemsPerColumn(items) {
  let itemsPerHour = {},
      itemsPerColumn = {},
      itemsCount = items.length,
      currentHour = 8,
      columnIndex = 1;

  items.forEach(item => {
    let start = moment(item.startHour),
        end = moment(item.endHour),
        startHour = start.format('H'),
        endHour = end.format('H');

    if (itemsPerHour[startHour] === undefined) { itemsPerHour[startHour] = []; }
    itemsPerHour[startHour].push({
      rowStart: startHour,
      rowEnd: endHour,
      item: item
    });
  });

  while (itemsCount > 0) {
    if (itemsPerHour[currentHour] !== [] && itemsPerHour[currentHour] !== undefined) {
      if (itemsPerColumn[columnIndex] === undefined) { itemsPerColumn[columnIndex] = []; }
      let nextHour = itemsPerHour[currentHour][0].rowEnd;
      itemsPerColumn[columnIndex].push(itemsPerHour[currentHour].shift());
      currentHour = nextHour - 1;
      itemsCount--;
    }
    if (currentHour === 18) {
      currentHour = 8;
      columnIndex++;
    }
    else currentHour++;
  }
  return itemsPerColumn;
}

Answer 1

您的问题类似于Interval scheduling .您可以找到像 this 这样的最佳解决方案。 (C++ 语言)。