Group multiple overlapping timeblocks that may not have a direct overlap

Question

I am trying to group timeslots by overlap but I can't figure out how to do it exactly.

I have a pretty simple array in the form of [{start_at: Date, end_at: Date, etc.etc. }]

And I lay them out in my view like this

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

Finding directly overlapping slots isn't that hard, I just compare a slot with the next one with (StartA <= EndB) and (EndA >= StartB) from here.

Now I want to group my overlapping slots (slot 1, 2, 3, 4 and 5) but not include slot 6 and 7, and put those two in their own group. into something like [[Slot (has 1 through 5)][Slot (has 6 and 7)]]

I am kind of lost with this problem right now and I hope anybody here can help me.

Answer 1

I'd suggest creating a Slot object that holds:

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

By keeping an up to date slot-range, you don't have to compare a new item to each of the slot's items. You'll only have to compare to the slot itself.

Now, you'll have to sort your items by start_at. You can then reduce the array by:

• Create a Slot for the first item
• Set the Slot's start_at and end_at to mimic those of the first item
• Go to the second item, check for overlap with the first Slot
  • If it overlaps,
    • push the second item to the Slot's items array, and
    • Set start_at to the minimum of Slot.start_at and item2.start_at
    • Do the same (max) for end_at
  • If it does not overlap,
    • Create a new Slot for the second item, repeat with this Slot and item3 (et cetera)

A sample implementation (I'd advice you to rewrite it based on your personal preferences. I didn't make any neat classes/prototypes/etc., nor did I test it 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 = [];
  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

I implemented a simple algorithm to group the slots regarding to the start and end values.

Here is a working fiddle https://jsfiddle.net/LeoAref/gg6q0mby/, and you will find a visual presentation for the grouping.

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

Answer 3

@user3297291's description/algorithm of a time interval grouping function is really good. Here's a function that was created/posted on GitHub by the user 'blaston' from several years ago that follows the algorithm. I'm posting it here in case the content/link disappears. I started with blaston's function for its simplicity to follow and swapped array groups in blaston's function for slot objects from @user3297291's post.

// Group all overlaping intervals
// * * * * * * *  
// This is an approach to a problem the engineers at Google Calandar/ Outlook probably faced. 
// You have events that may overlap and you want to display them in such a way that 
// they don't overlap with each other. One approach is to distribute them into columns. 
// Each column has events that don't overlap with each other.

// Cost: O(n*log n) if the interval aren't sorted by the starting time, 
//   O(n) otherwise.
// Sample run: groupOverlapingIntervals([ [2, 5], [5, 6],[3, 4] ])
// Output: [ [ [2, 5], [3, 4], [5, 6] ] ]

function groupOverlapingIntervals(intervals) {
  intervals.sort(function(a, b) {
    return a[0] - b[0];
  });

  var groups = [
    [intervals[0]]
  ];
  var j = 0;
  var end = intervals[0][1];

  for (var i = 1; i < intervals.length; i++) {
    if (intervals[i][0] <= end) {
      if (intervals[i][1] > end) {
        end = intervals[i][1];
      }
      groups[j].push(intervals[i]);
    } else {
      groups.push([intervals[i]]);
      j++;
      end = intervals[i][1];
    }
  }
  return groups;
}

var intervals = [
  [2, 5],
  [5, 6],
  [3, 4],
  [7, 8],
  [6.5, 9],
  [10, 11.5]
];
var groups = groupOverlapingIntervals(intervals);
console.log(groups);