javascript - 对可能没有直接重叠的多个重叠时间 block 进行分组

Question

我正在尝试通过重叠对时间段进行分组，但我不知道如何准确地做到这一点。

我有一个非常简单的数组，形式为 [{start_at: Date, end_at: Date, etc.etc. }]

我将它们放在我的 View 中，如下所示

<---slot1----><----slot5----><--slot6-->
  <--slot2-><--slot4--->            <--slot7-->
    <----slot3---->

查找直接重叠的插槽并不难，我只需将一个插槽与下一个插槽进行比较 (StartA <= EndB) and (EndA >= StartB) from here .

现在我想对重叠的插槽(插槽 1、2、3、4 和 5)进行分组，但不包括插槽 6 和 7，并将这两个插槽放入自己的组中。变成像[[Slot (has 1 through 5)][Slot (has 6 and 7)]]这样的东西

我现在对这个问题有点迷失，我希望这里的任何人都可以帮助我。

Answer 1

我建议创建一个包含以下内容的 Slot 对象:

• 插槽中项目的数组，
• 这些项目的最早start_at日期，
• 这些项目的最新 end_at。

通过保持最新的槽位范围，您不必将新项目与槽位的每个项目进行比较。您只需与插槽本身进行比较即可。

现在，您必须按 start_at 对项目进行排序。然后您可以通过以下方式减少数组:

• 为第一个项目创建一个槽位
• 设置Slot的start_at和end_at以模仿第一个项目的start_at和end_at
• 转到第二个项目，检查是否与第一个Slot重叠
  • 如果重叠，
    • 将第二个项目插入Slot的项目数组，并且
    • 将 start_at 设置为 Slot.start_at 和 item2.start_at 中的最小值
    • 对 end_at 执行相同的操作(最多)
  • 如果不重叠，
    • 为第二个项目创建一个新的Slot，重复此Slot和item3(等等)

示例实现(我建议您根据个人喜好重写它。我没有制作任何简洁的类/原型(prototype)等，也没有对其进行彻底测试)

function createSlot(initialItem) {
 var slot = {
   items: [initialItem],
   start: initialItem.start,
   end: initialItem.end
 };
  
  slot.addItem = function(item) {
    slot.items.push(item);
    slot.start = Math.min(slot.start, item.start);
    slot.end = Math.max(slot.end, item.end);
  }
  
  return slot;
};
  
function itemsOverlap(item1, item2) {
  return item1.start <= item2.end &&
    item1.end >= item2.start;
};

var slots = [];
var items = randomItems(10);


items.slice(1).reduce(function(currentSlot, item) {
  if (itemsOverlap(currentSlot, item)) {
    currentSlot.addItem(item); 
    return currentSlot;
  }
  
  slots.push(currentSlot);
  return createSlot(item);
}, createSlot(items[0]));

console.log(
  slots.map(function(slot) { return slot.items.length; }));



// Create random data
function randomItems(n) {
  var arr = [];
  for (var i = 0; i < n; i += 1) {
   arr.push(generateRandomItem()); 
  }
  return arr.sort(function(a, b) { return a.start - b.start; });
};


function randomHourTimespan() {
  return Math.random() * 60 * 60 * 1000;
};

function randomHalfDayTimespan() {
  return randomHourTimespan() * 12;
};

function generateRandomItem() {
  var start = Date.now() + randomHalfDayTimespan();
  var end = start + randomHourTimespan();
  
  return { start: new Date(start), end: new Date(end) };
}