Bug in Timeline Gap-Detection Algorithm

Question

I have an algorithm that examines an array of Event (StartTime,EndTime) on a timeline that runs from Midnight->Midnight to check for any gaps. The algorithm works, but there is one configuration where it doesn't work.

Before I show the code, here's the specific case where it doesn't work: When I have a Midnight-ending Event with the same StartTime as another event which does not end at midnight. The problem here is that I add an erroneous GAP to my result, a GAP (Midnight,Midnight). It shouldn't be there in my result.

Now the code: All Events (including GAP Events) have a (StartTime,EndTime). I am receiving an incoming array of normal proposedEvents, and my job is to return a filled-out array of preparedGapEvents.

function schedulerPrepareGapEvents(proposedEvents) {

var preparedGapEvents = [];

// First sort proposed events by StartTime
proposedEvents.sort(sortObjectsByStartTime); // sort by StartTime of the event

// If there are no proposed events, exit immediately with an empty result
if (proposedEvents.length == 0) {
    return preparedGapEvents;
}   

// Manually add first gap, if it exists: Sorted Proposed Event #1 not starting at 12:00am
var startTimeFirst = getTimestampFromString(proposedEvents[0].startTime);
if (startTimeFirst > 0) {
    preparedGapEvents.push({"gapEventID" : "event-GAP" + generateUniqueID(), 
                            "gapEventColor" : globalGapEventColor, 
                            "gapEventStartTimestamp" : 0, 
                            "gapEventEndTimestamp" : startTimeFirst});      
}

// Initially lastMaxEndTime is the End Time of 1st Event
var lastMaxEndTime = getTimestampFromString(proposedEvents[0].endTime); 

// Main Event Traversal Loop
jQuery.each(proposedEvents, function(index, item) {     

    // Get the current proposed event's StartTime/EndTime in the loop
    var startTimeCurrent = getTimestampFromString(item.startTime);
    var endTimeCurrent = getTimestampFromString(item.endTime);

    // Next neighboring proposed event
    var nextEvent = proposedEvents[index+1];

    // If Next Proposed Event exists
    if (nextEvent != null) {
        var startTimeNext = getTimestampFromString(nextEvent.startTime);
        var endTimeNext = getTimestampFromString(nextEvent.endTime);

        if (startTimeNext > lastMaxEndTime) { // Gap detected! 
            preparedGapEvents.push({"gapEventID" : "event-GAP" + generateUniqueID(), 
                                    "gapEventColor" : globalGapEventColor,
                                    "gapEventStartTimestamp" : lastMaxEndTime, 
                                    "gapEventEndTimestamp" : startTimeNext});               
        }

        // Keep track of the current MAX EndTime: either this new event's EndTime or the previous Max EndTime
        lastMaxEndTime = Math.max(lastMaxEndTime, endTimeNext);
    }
    else {
        // Last Proposed Event (no next neighbor): its End Time must be at the 24-hr END mark, otherwise a gap
        if (endTimeCurrent < 1440) {
            preparedGapEvents.push({"gapEventID" : "event-GAP" + generateUniqueID(), 
                                    "gapEventColor" : globalGapEventColor,
                                    "gapEventStartTimestamp" : lastMaxEndTime, 
                                    "gapEventEndTimestamp" : 1440});
        }
    }
}); 

return preparedGapEvents;

The problem here is somewhere in the main loop. After I sort by StartTime, the two adjoining events can be either in Position 0 or 1, depending on chance. Suppose that by chance I have a neighbor in the +1 position that I will examine. In that case, I fall into the ELSE, and satisfy the condition if (endTimeCurrent < 1440) because that event's End Time is not 1440 (Midnight)!

So how do I fix this?

user_2862341 · Answer

This is what I understood -

There are 'events' in the 24 hour window.
Events have start time and end time.
If there are no events then its a 'GAP'.
A 'GAP' is also considered an event.
There can be concurrent events (two atleast from the diagram that you have given).
With regard the positions '0' and '1' I'm assuming they refer to the blue and red section in the figure in your question.

The problem statement is that you're trying to identify 'GAP' times and list them out. You've bulit the above algorithm to do that. From what I've gathered, it (identification of gaps) does not work for concurrent events (in one of the positions) since the overlap is not handled.

One way to handle overlapping events would be as follows - identify which of the events are smaller in duration and remove that event.

Also its not clear why you consider 1440 as midnight. It refers to 2:20 PM does it not ?

Regards,

Ravindra

user_753642 · Answer

I define a task as (something which has a start date and an end date)
I redefine an event as something which occured : a task started or ended

What you may want to do is travel along t, and sort your events accordingly (be they start task but also task end)

Consider the following timeline

---------------->t
 O----X
   O-----X
   O------------X

Where O stands for a starting task, and X for ending

This is very similar to checking whether your html is valid: If you encounter an opening tag but presently there is no open tag ongoing, then you have a gap.

So algorithm be like:

events = []
forall tasks as start, end:
    events.push({start: true, at: start}, {start:false, at:end})

sort the events as:
    first by t time
    in case two events have the same t,
    opening events should come before closing ones
forall events:
    when a start task: 
        if openTagCounter == 0 //and different than init
            gaps.push(lastClosedAt, task.start)
        openTagCounter++
    when a end task:
        openTagCounter--
        if openTagCounter == 0
            lastClosedAt = task.end

You can handle the eventual gap at the beginning and at the start

if startDay < events[0].start
    gaps.push(guess what)
if last(events).end < endDay
    gaps.push(same)

function getGaps(startDay, endDay, tasks){
    let events = tasks.flatMap(t=>{
        return [{ref: t, at: t.start, start:true},{ref: t, at: t.end, start:false}]
    },[]);

    events.sort((a,b)=>{
        if(a.at!=b.at) return a.at-b.at;
        return a.start?-1:0;
    });

    let gaps = [];
    let lastClosed = 0;//lastClosed only truthy if start of a gap
    let anyOpened = 0;
    events.forEach(ev=>{
        if(ev.start){
            anyOpened++;
            if(lastClosed){
                gaps.push({start: lastClosed, end: ev.at});
                lastClosed = false;
            }
        }else{
            anyOpened--;
            if(anyOpened == 0){
                lastClosed = ev.at;
            }
        }
    });

    //finally handle the first gap, and the last gap
    if(startDay != events[0].at){
        gaps.push({start: startDay, end: events[0].at})
    }
    if(endDay != events[events.length-1].at){
        gaps.push({start: events[events.length-1].at, end: endDay})   
    }
    return gaps;
}
console.log(getGaps(0, 24, [
    {start:23, end:23.5},
    {start:23, end:24},
]))
//[ { start: 0, end: 23 } ]
console.log(getGaps(0, 24, [
    {start:23, end:24},
    {start:23, end:23.5},
]))
//[ { start: 0, end: 23 } ]
console.log(getGaps(0, 24, [
    {start:23, end:23.7},
    {start:23, end:23.5},
]))
//[ { start: 0, end: 23 }, { start: 23.7, end: 24 } ]
console.log(getGaps(0, 24, [
    {start:23, end:23.5},
    {start:23.5, end:23.7},
    {start:23, end:23.5},
    {start:23.5, end:23.7},
]))
//[ { start: 0, end: 23 }, { start: 23.7, end: 24 } ]

user_7696162 · Answer

Here's another take... It simplifies the schedulerPrepareGapEvents function main loop by only checking whether the startTime is greater than the lastMaxEndTime, and adding the gap accordingly. Then, once the loop is complete, the function simply checks if there is a gap between lastMaxEndTime and midnight (1440 minutes).

// Filler functions to support testing...
var uid = 1;
function generateUniqueID() { return uid++};
function getTimestampFromString(x) {return x};
var globalGapEventColor = 123;

// Function to seek gaps between events.
function schedulerPrepareGapEvents(proposedEvents) {

  // First sort proposed events by StartTime
  proposedEvents.sort((a, b) => getTimestampFromString(a.startTime) - getTimestampFromString(b.startTime)); // sort by StartTime of the event

  // Initialize lastMaxEndTime to the beginning of the time interval
  var lastMaxEndTime = 0;
  var preparedGapEvents = [];

  // Main Event Traversal Loop
  for (var index = 0; index < proposedEvents.length; index++) {

    var item = proposedEvents[index];

    // Get the current proposed event's StartTime/EndTime in the loop
    var startTimeCurrent = getTimestampFromString(item.startTime);
    var endTimeCurrent = getTimestampFromString(item.endTime);

    // If the startTime is greater than the last max end time, add as a gap.
    if (lastMaxEndTime < startTimeCurrent) { // Gap detected! 
        preparedGapEvents.push({"gapEventID" : "event-GAP" + generateUniqueID(), 
                                "gapEventColor" : globalGapEventColor,
                                "gapEventStartTimestamp" : lastMaxEndTime, 
                                "gapEventEndTimestamp" : startTimeCurrent});               
    }

    lastMaxEndTime = Math.max(lastMaxEndTime, endTimeCurrent);
  }

  // Finally, add any gap up to midnight.
  if (lastMaxEndTime < 1440) {
      preparedGapEvents.push({"gapEventID" : "event-GAP" + generateUniqueID(), 
                              "gapEventColor" : globalGapEventColor,
                              "gapEventStartTimestamp" : lastMaxEndTime, 
                              "gapEventEndTimestamp" : 1440});
  }
        
  return preparedGapEvents;
}

// Run test...
console.log("Test 1:");
var pe0 = [{startTime: 22*60, endTime: 24*60}, {startTime: 22*60, endTime: 23*60}];
console.log( schedulerPrepareGapEvents( pe0 ) );

console.log("Test 2:");
var pe1 = [{startTime: 22*60, endTime: 23*60}, {startTime: 22*60, endTime: 24*60}];
console.log( schedulerPrepareGapEvents( pe1 ) );

Hope this helps...

Bug in Timeline Gap-Detection Algorithm

3 Answers