使用PHP检测日历事件重叠冲突

Question

I am working on a feature that checks if external events collide with internal events (in a calendar app). The process looks like this:

• My application creates an array of possible events (called $internalEvents)
• I source external events from calendars such as Google Calendar, iCloud, etc. (called $externalEvents). These are existing events with the type busy.
• Now I have to check if there is any kind of conflict regarding internal and external events. I tried something as you can see below but this is by far not correct or bulletproof.

I tried to reduce it to the minimum as much as possible. This is the data input:

$internalEvents = array(
    array(
        "start" => "03/29/2016 12:00:00",
        "end" => "03/29/2016 13:00:00"
    ),
    array(
        "start" => "03/29/2016 12:30:00",
        "end" => "03/29/2016 13:30:00"
    ),
    array(
        "start" => "03/29/2016 13:00:00",
        "end" => "03/29/2016 14:00:00"
    ),
    array(
        "start" => "03/29/2016 13:30:00",
        "end" => "03/29/2016 14:50:00"
    ),
    array(
        "start" => "03/29/2016 14:00:00",
        "end" => "03/29/2016 15:00:00"
    ),
    array(
        "start" => "03/29/2016 14:30:00",
        "end" => "03/29/2016 15:30:00"
    ),
    array(
        "start" => "03/29/2016 15:00:00",
        "end" => "03/29/2016 16:00:00"
    ),
    array(
        "start" => "03/29/2016 15:30:00",
        "end" => "03/29/2016 16:30:00"
    ),
    array(
        "start" => "03/29/2016 16:00:00",
        "end" => "03/29/2016 17:00:00"
    )
);

$externalEvents = array(
    array(
        "start" => "03/29/2016 08:00:00",
        "end" => "03/29/2016 12:00:00",
        "type" => "busy"
    ),
    array(
        "start" => "03/29/2016 15:30:00",
        "end" => "03/29/2016 16:00:00",
        "type" => "busy"
    ),
    array(
        "start" => "03/29/2016 13:30:00",
        "end" => "03/29/2016 14:15:00",
        "type" => "busy"
    )
);

Now I try to find any kind of conflict by comparing the internal event to all external events:

foreach($internalEvents as $internalEvent) {

    $internalEventStart = new DateTime($internalEvent['start']);
    $internalEventEnd = new DateTime($internalEvent['end']);

    $result = true;

    echo "
verifying " . $internalEventStart->format('Y-m-d H:i') . " - " . $internalEventEnd->format('Y-m-d H:i') . "
";

    foreach($externalEvents as $externalEvent) {
        $externalEventStart = new DateTime($externalEvent['start']);
        $externalEventEnd = new DateTime($externalEvent['end']);

        // check if there are conflicts between internal and external events
        if ($internalEventStart >= $externalEventStart && $internalEventStart <= $externalEventEnd) {
            $result = false;
            echo "   problem 1: event is between busy time: " . "
";
        }

        if ($internalEventStart >= $externalEventStart && $internalEventStart <= $externalEventEnd && $externalEventEnd <= $internalEventEnd) {
            $result = false;
            echo "   problem 2: event starts during busy time: " . "
";
        }

        if ($internalEventStart <= $externalEventStart && $externalEventStart <= $internalEventEnd && $internalEventEnd <= $externalEventEnd) {
            $result = false;
            echo "   problem 3: event stops during busy time: " . "
";
        }

        if (($internalEventStart <= $externalEventStart) && ($externalEventStart <= $externalEventEnd) && ($externalEventEnd <= $internalEventEnd)) {
            $result = false;
            echo "   problem 4: event during busy time: " . "
";
        }

        if (($internalEventStart <= $internalEventEnd) && ($internalEventEnd <= $externalEventStart) && ($externalEventStart <= $externalEventEnd)) {
            $result = false;
            echo "   problem 5: event during busy time: " . "
";
        }
    }

    if($result) {
        echo "   result: OK
";
    } else {
        echo "   result: NOT OK 
";
    }
}

I am looking for an algorithm that can find any possible event overlap conflict. Any hint is highly appreciated.

The running code can be found here (IDEone.com).

Answer 1

When two events collide? See this schema:

                              ----E----                 CS/EE   CE/ES
                        --N--                             <       <
                                        --N--             >       >
                           --C--                          <       >
                                     --C--                <       >
                                --C--                     <       >
                             -----C-----                  <       >
                    ··················································
                    E  = Main Event
                    N  = Not Collide Event
                    C  = Collide Event
                    CS = Compare Event Start
                    EE = Main Event End
                    CE = Compare Event End
                    ES = Main Event Start

As you can see, there is collision only when the start of event C is before the end of event E and the end of event E is after the start of event C. Knowing this helps to find an efficient and short method to compare events.

About the code, a preliminary note: you convert the dates in ISO 8601 before comparing it multiple times in your code, so why do not create a function for this?

function eventsToDate( $row )
{
    $retval = array( 'start' => date_create( $row['start'] )->format('Y-m-d H:i:s'), 'end' => date_create( $row['end'] )->format('Y-m-d H:i:s') );
    $retval['print'] = sprintf( '%s-%s', substr( $retval['start'],-8,5 ), substr( $retval['end'],-8,5 ) );
    return $retval;
}

This function returns an associative array with 'start' and 'end' in your format. I have added a third key, 'print', to use during debug. Note that in the print I consider only hours:minutes (all the dates in your array sample are from same day), but the comparison is made on complete dates. You can omit this 'print' key or replace it with preferred output format.

You execute two nested foreach, and for each loop recalculate the date format. With your array samples, you call DateTime/DateTime::format 36 times. By creating a temporary array with all converted $externalEvents, we can reduce these calls to 12. So, before starting foreach() loop, we use array_map with above custom function and $externalEvents array to create an array with formatted dates:

$externalDates = array_map( 'eventsToDate', $externalEvents );

Then, we start the main foreach() loop on $internalEvents:

foreach( $internalEvents as $internalEvent )
{
    $internalDates = eventsToDate( $internalEvent );

    echo $internalDates['print'] . PHP_EOL;
    $result = True;
    foreach( $externalDates as $externalDate )
    {

At this point, we compare dates. As mentioned above, we compare start with end and end with start. To simplify next comparison, we use strcmp, a php function that “returns < 0 if str1 is less than str2, > 0 if str1 is greater than str2, and 0 if they are equal”:

        $startCmp = strcmp( $internalDates['start'], $externalDate['end'] );
        $endCmp   = strcmp( $internalDates['end'],   $externalDate['start']   );

Now, the comparison:

        if( $startCmp<0 && $endCmp>0 )
        {
            $result = False;
            echo "           {$externalDate['print']} COLLIDE
";
        }
        else
        {
            echo "           {$externalDate['print']} OK
";
        }
    }

And, finally, we can print the result:

    echo "Result: " . ( $result ? 'OK' : 'NOT OK') . "

";
}

<kbd>eval.in demo</kbd>

Note: with above comparison, with first $internalEvent we obtain following result:

12:00-13:00
           08:00-12:00 OK
           15:30-16:00 OK
           13:30-14:15 OK
Result: OK

Instead, if you want this result:

12:00-13:00
           08:00-12:00 COLLIDE
           15:30-16:00 OK
           13:30-14:15 OK
Result: NOT OK

You have to replace above if condition with this:

         if( $startCmp<=0 && $endCmp>=0 )

Above code will work, if you want more details about kind of collision, you can test other combinations of start/end inside if condition.

---

Alternative: Return Colliding Events

If — instead of printing results — you want catch colliding events, you can replace nested foreach() with array_filter in this way:

$result = array_filter
(
    $externalDates, 
    function( $row ) use( $internalDates )
    {
        $startCmp = strcmp( $internalDates['start'], $row['end'] );
        $endCmp   = strcmp( $internalDates['end'],   $row['start']   );
        return( $startCmp<0 && $endCmp>0 );
    }
);

At this point, colliding events are in array $result. Obviously, is the array is empty, there are not collisions.

---

• Read more about strcmp()
• Read more about array_map()
• Read more about array_filter()