javascript - Group multiple overlapping timeblocks that may not have a direct overlap -

i trying group timeslots overlap can't figure out how exactly.

i have pretty simple array in form of [{start_at: date, end_at: date, etc.etc. }]

and lay them out in view this

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

finding directly overlapping slots isn't hard, compare slot next 1 (starta <= endb) , (enda >= startb) from here.

now want group overlapping slots (slot 1, 2, 3, 4 , 5) not include slot 6 , 7, , put 2 in own group. [[slot (has 1 through 5)][slot (has 6 , 7)]]

i kind of lost problem right , hope here can me.

i'd suggest creating slot object holds:

• an array of items in slot,
• the earliest start_at date of items,
• the latest end_at of items.

by keeping date slot-range, don't have compare new item each of slot's items. you'll have compare slot itself.

now, you'll have sort items start_at. can reduce array by:

• create slot first item
• set slot's start_at , end_at mimic of first item
• go second item, check overlap first slot
  • if overlaps,
    • push second item slot's items array, and
    • set start_at minimum of slot.start_at , item2.start_at
    • do same (max) end_at
  • if not overlap,
    • create new slot second item, repeat slot , item3 (et cetera)

a sample implementation (i'd advice rewrite based on personal preferences. didn't make neat classes/prototypes/etc., nor did test thoroughly)

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 = [];    (var = 0; < n; += 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) };  }