Overlapping event search algorithm / times

Question

While working with a custom calendar, I can't figure out how to find time intervals that span any other time interval.

Time intervals start from 0 to 720 (from 9 a.m. to 9 p.m., each pixel is a minute).

var events = [ {id : 1, start : 0, end : 40}, // an event from 9:00am to 9:40am {id : 2, start : 30, end : 150}, // an event from 9:30am to 11:30am {id : 3, start : 20, end : 180}, // an event from 9:20am to 12:00am {id : 4, start : 200, end : 230}, // an event from 12:20pm to 12:30pm {id : 5, start : 540, end : 600}, // an event from 6pm to 7pm {id : 6, start : 560, end : 620} // an event from 6:20pm to 7:20pm ]; 

Each time interval is one hour, for example, from 9 to 10, from 10 to 11, from 11 to 12, etc.

In the above example, the three events (id: 1,2,3) overlap for the start times of 9-10 : 9:00 , 9:30 and 9:20 . And other overlapping events are time intervals from 6 to 7 (id: 5, 6) with launch times of 6 and 6:20 . An event with id 4 has no overlapping events in the time interval from 12 to 1 .

I am looking for a way to get all overlapping event IDs, as well as the number of events in a particular time interval, this is the expected result:

 [ {id:1, eventCount: 3}, {id:2, eventCount: 3}, {id:3, eventCount: 3}, {id:5, eventCount: 2}, {id:6, eventCount: 2} ] 

For identifiers (1 to 3), there are events 3 for time intervals 9 to 10 and 2 for time interval 6 - 7 .

I created this formula to convert a temporary number to an actual time:

 var start_time = new Date(0, 0, 0, Math.abs(events[i].start / 60) + 9, Math.abs(events[i].start % 60)).toLocaleTimeString(), var end_time = new Date(0, 0, 0, Math.abs(events[i].end / 60) + 9, Math.abs(events[i].end % 60)).toLocaleTimeString(); 

This is what I have so far:

 function getOverlaps(events) { // sort events events.sort(function(a,b){return a.start - b.start;}); for (var i = 0, l = events.length; i < l; i++) { // cant figure out what should be next } } 

DEMO if you need to.

Answer 1

from my jquery-week-calendar commit , here is how I do it:

  _groupOverlappingEventElements: function($weekDay) { var $events = $weekDay.find('.wc-cal-event:visible'); var complexEvents = jQuery.map($events, function (element, index) { var $event = $(element); var position = $event.position(); var height = $event.height(); var calEvent = $event.data('calEvent'); var complexEvent = { 'event': $event, 'calEvent': calEvent, 'top': position.top, 'bottom': position.top + height }; return complexEvent; }).sort(function (a, b) { var result = a.top - b.top; if (result) { return result; } return a.bottom - b.bottom; }); var groups = new Array(); var currentGroup; var lastBottom = -1; jQuery.each(complexEvents, function (index, element) { var complexEvent = element; var $event = complexEvent.event; var top = complexEvent.top; var bottom = complexEvent.bottom; if (!currentGroup || lastBottom < top) { currentGroup = new Array(); groups.push(currentGroup); } currentGroup.push($event); lastBottom = Math.max(lastBottom, bottom); }); return groups; } 

there is a bit of noise specific to the component, but you get the logic:

• sort events by their start ascending
• sort events by their end ascending
• iterate over the sorted events and check the beginning / end of the previous event (performed rather by the position than by the properties of the event itself - just because the design can overlap, but the events aren’t ... for example: creating a 2px border, events with non-overlapping start / end times can overlap or “touch”)
• each overlapping group ( currentGroup ) is a new array inside groups -array

soo ... your code may look like this (by the way, you don't need to work with real date -instances)

 events.sort(function (a, b) { var result = a.start - b.start; if (result) { return result; } return a.end - b.end; }); var groups = new Array(); var currentGroup; var lastEnd = -1; jQuery.each(events, function (index, element) { var event = element; var start = event.start; var end = event.end; if (!currentGroup || lastEnd < start) { currentGroup = new Array(); groups.push(currentGroup); } currentGroup.push(event); lastEnd = Math.max(lastEnd, end); }); return groups; 

soo ... you do not want to push your own energy to your problem ... well

 var output = new Array(); jQuery.each(groups, function (index, element) { var group = element; if (group.length <= 1) { return; } jQuery.each(group, function (index, element) { var event = element; var foo = { 'id': event.id, 'eventCount': group.length }; output.push(foo); }); }); 

Answer 2

It’s easier for me to use timestamps for each start and end event, so you can directly work with them or change them to date objects. To get the value, create a date object for each beginning and end, and then:

 var a.start = startDate.getTime(); var a.end = endDate.getTime(); 

To overlap:

 if (a.start <= b.start && a.end > b.start || a.start < b.end && a.end >= b.end) { // a overlaps b } 

You can leave them as date objects, if you want, the above will work just as well.

Edit

Ok here's a working example:

Assuming a nominal date of 2012-05-15, the array of events is as follows:

 // Use iso8601 like datestring to make a local date object function getDateObj(s) { var bits = s.split(/[- :]/); var date = new Date(bits[0], bits[1] - 1, bits[2]); date.setHours(bits[3], bits[4], 0); return date; } var events = [ {id: 1, start: getDateObj('2012-05-15 09:00'), end: getDateObj('2012-05-15 09:30')}, {id: 2, start: getDateObj('2012-05-15 09:30'), end: getDateObj('2012-05-15 11:30')}, {id: 3, start: getDateObj('2012-05-15 09:20'), end: getDateObj('2012-05-15 12:00')}, {id: 4, start: getDateObj('2012-05-15 12:20'), end: getDateObj('2012-05-15 12:30')}, {id: 5, start: getDateObj('2012-05-15 18:00'), end: getDateObj('2012-05-15 19:00')}, {id: 6, start: getDateObj('2012-05-15 18:20'), end: getDateObj('2012-05-15 19:20')} ]; function getOverlappingEvents(eventArray) { var result = []; var a, b; // Sort the event array on start time eventArray.sort(function(a, b) { return a.start - b.start; }); // Get overlapping events for (var i=0, iLen=eventArray.length - 1; i<iLen; i++) { a = eventArray[i]; b = eventArray[i + 1]; if ((a.start <= b.start && a.end > b.start) || (a.start < b.end && a.end >= b.end) ) { result.push([a.id, b.id]); } } return result; } // Run it alert(getOverlappingEvents(events).join('\n')); // 1,3 2,3 5,6 

Answer 3

Here is the code that will do what you want. As already mentioned, you were probably better served by storing date objects, but that is another problem.

 function getOverlaps(events) { // sort events events.sort(function (a, b) { return a.start - b.start; }); var results = []; for (var i = 0, l = events.length; i < l; i++) { var oEvent = events[i]; var nOverlaps = 0; for (var j = 0; j < l; j++) { var oCompareEvent = events[j]; if (oCompareEvent.start <= oEvent.end && oCompareEvent.end > oEvent.start || oCompareEvent.end <= oEvent.start && oCompareEvent.start > oEvent.end) { nOverlaps++; } } if (nOverlaps > 1) { results.push({ id: oEvent.id, eventCount: nOverlaps, toString: function () { return "[id:" + this.id + ", events:" + this.eventCount + "]" } }); } } return results; }