將可能沒有直接重疊的多個重疊時間組分組

Question

我想通過重疊對時間組進行分組，但我無法弄清楚如何完全做到這一點。

我在[{start_at: Date, end_at: Date, etc.etc. }]

形式非常簡單的數組，我躺在出來，我認爲這樣的

<---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對象保存：

• 在插槽項目的array，
• 這些項目的最早日期start_at，
• 這些項目的最新end_at。

通過保持最新的插槽範圍，您不必將新項目與每個插槽項目進行比較。你只需要比較插槽本身。

現在，您必須按start_at排序項目。然後，您可以減少由數組：

• 的第一個項目
• 設置Slot的start_at和end_at模仿者中的第一項
• 轉到第二個項目的創建Slot，檢查與第一Slot
  • 如果重疊，
    • 推的S重疊的Econd項目的Slot的項目陣列，以及
    • 設置start_at到最小的Slot.start_at和item2.start_at
    • 做同樣的（最大）end_at
  • 如果不重疊，
    • 爲第二項創建新的Slot，以此重複Slot和item3（等等）

實現示例（我建議你根據你的個人喜好來重寫。我沒有做任何整齊的類/原型的/ etc。，我也沒有測試它徹底）

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

Answer 2

我實現了一個簡單的算法組的插槽關於向start和end值。

這裏是一個工作小提琴https://jsfiddle.net/LeoAref/gg6q0mby/，你會發現一個視覺呈現的分組。

var timeSlots = [ 
    {start: 0, end: 3}, 
    {start: 1, end: 2}, 
    {start: 2, end: 4}, 
    {start: 4, end: 6}, 
    {start: 4, end: 8}, 
    {start: 5, end: 6} 
]; 

timeSlots.forEach((slot, index) => { 
    var slotElem = document.createElement('div'); 

    slotElem.classList.add('slot'); 
    slotElem.style.top = index * 25 + 'px'; 
    slotElem.style.left = slot.start * 30 + 'px'; 
    slotElem.style.width = (slot.end - slot.start) * 30 + 'px'; 

    document.body.appendChild(slotElem); 
}); 

var groups = []; 

timeSlots.forEach(slot => { 
    added = false; 

    if (groups.length) { 
    var index = 0; 

    do { 
     group = groups[index]; 

     if (slot.start >= group.start && slot.start < group.end || 
      slot.end <= group.end && slot.end > group.start 
    ) { 
     group.slots.push(slot); 

     group.start = Math.min(slot.start, group.start); 
     group.end = Math.max(slot.end, group.end); 

     added = true; 
     } 
    } while (!added && ++index < groups.length); 

    if (!added) { 
     groups.push({start: slot.start, end: slot.end, slots: [slot]}); 
    } 
    } else { 
    groups.push({start: slot.start, end: slot.end, slots: [slot]}); 
    } 
}) 

groups.forEach(group => { 
    var groupElem = document.createElement('div'); 

    groupElem.classList.add('group'); 
    groupElem.style.left = group.start * 30 + 'px'; 
    groupElem.style.width = (group.end - group.start) * 30 - 2 + 'px'; 

    document.body.appendChild(groupElem); 
})