PHP Determine when multiple(n) datetime ranges overlap each other

Question

I'm having a hell of a time trying to solve the following problem:

It's a calendar program where given a set of available datetime sets from multiple people, I need to figure out what datetime ranges everyone is available in PHP

Availability Sets:

p1: start: "2016-04-30 12:00", end: "2016-05-01 03:00"

p2: start: "2016-04-30 03:00", end: "2016-05-01 03:00"

p3: start: "2016-04-30 03:00", end: "2016-04-30 13:31"
    start: "2016-04-30 15:26", end: "2016-05-01 03:00"

I'm looking for a function that I can call that will tell me what datetime ranges all (p) people are available at the same time.

In the above example the answer should be:

2016-04-30 12:00 -> 2016-04-30 13:31
2016-04-30 15:26 -> 2016-05-01 03:00

I did find this similar question and answer Datetime -Determine whether multiple(n) datetime ranges overlap each other in R

But I have no idea what language that is, and have to unable to translate the logic in the answer.

Answer 1

Well that was fun. There's probably a more elegant way of doing this than looping over every minute, but I don't know if PHP is the language for it. Note that this currently needs to manage the start and end times to search separately, although it would be fairly trivial to calculate them based on the available shifts.

<?php
$availability = [
    'Alex' => [
        [
            'start' => new DateTime('2016-04-30 12:00'),
            'end'   => new DateTime('2016-05-01 03:00'),
        ],
    ],

    'Ben' => [
        [
            'start' => new DateTime('2016-04-30 03:00'),
            'end'   => new DateTime('2016-05-01 03:00'),
        ],
    ],

    'Chris' => [
        [
            'start' => new DateTime('2016-04-30 03:00'),
            'end'   => new DateTime('2016-04-30 13:31')
        ],

        [
            'start' => new DateTime('2016-04-30 15:26'),
            'end'   => new DateTime('2016-05-01 03:00')
        ],
    ],
];

$start = new DateTime('2016-04-30 00:00');
$end   = new DateTime('2016-05-01 23:59');
$tick  = DateInterval::createFromDateString('1 minute');

$period = new DatePeriod($start, $tick, $end);

$overlaps = [];
$overlapStart = $overlapUntil = null;

foreach ($period as $minute)
{
    $peopleAvailable = 0;

    // Find out how many people are available for the current minute
    foreach ($availability as $name => $shifts)
    {
        foreach ($shifts as $shift)
        {
            if ($shift['start'] <= $minute && $shift['end'] >= $minute)
            {
                // If any shift matches, this person is available
                $peopleAvailable++;
                break;
            }
        }
    }

    // If everyone is available...
    if ($peopleAvailable == count($availability))
    {
        // ... either start a new period...
        if (!$overlapStart)
        {
            $overlapStart = $minute;
        }

        // ... or track an existing one
        else
        {
            $overlapUntil = $minute;
        }
    }

    // If not and we were previously in a period of overlap, end it
    elseif ($overlapStart)
    {
        $overlaps[] = [
            'start' => $overlapStart,
            'end'   => $overlapUntil,
        ];

        $overlapStart = null;
    }
}

foreach ($overlaps as $overlap)
{
    echo $overlap['start']->format('Y-m-d H:i:s'), ' -> ', $overlap['end']->format('Y-m-d H:i:s'), PHP_EOL;
}

Answer 2

There are some bugs with this implementation, see the comments. I'm unable to delete it as it's the accepted answer. Please use iainn or fusion3k's very good answers until I get around to fixing it.

There's actually no need to use any date/time handling to solve this problem. You can exploit the fact that dates in this format are in alphabetical as well as chronological order.

I'm not sure this makes the solution any less complex. It's probably less readable this way. But it's considerably faster than iterating over every minute so you might choose it if performance is a concern.

You also get to use every single array function out there, which is nice.

Of course, because I haven't used any date/time functions, it might not work if Daylight Savings Time or users in different time zones need dealing with.

$availability = [
    [
        ["2016-04-30 12:00", "2016-05-01 03:00"]
    ],
    [
        ["2016-04-30 03:00", "2016-05-01 03:00"]
    ],
    [
        ["2016-04-30 03:00", "2016-04-30 13:31"],
        ["2016-04-30 15:26", "2016-05-01 03:00"]
    ]
];

// Placeholder array to contain the periods when everyone is available.
$periods = [];

// Loop until one of the people has no periods left.
while (count($availability) &&
       count(array_filter($availability)) == count($availability)) {
    // Select every person's earliest date, then choose the latest of these
    // dates.
    $start = array_reduce($availability, function($carry, $ranges) {
        $start = array_reduce($ranges, function($carry, $range) {
            // This person's earliest start date.
            return !$carry ? $range[0] : min($range[0], $carry);
        });
        // The latest of all the start dates.
        return !$carry ? $start : max($start, $carry);
    });

    // Select each person's range which contains this date.
    $matching_ranges = array_filter(array_map(function($ranges) use($start) {
        return current(array_filter($ranges, function($range) use($start) {
            // The range starts before and ends after the start date.
            return $range[0] <= $start && $range[1] >= $start;
        }));
    }, $availability));

    // Find the earliest of the ranges' end dates, and this completes our
    // first period that everyone can attend.
    $end = array_reduce($matching_ranges, function($carry, $range) {
        return !$carry ? $range[1] : min($range[1], $carry);
    });

    // Add it to our list of periods.
    $periods[] = [$start, $end];

    // Remove any availability periods which finish before the end of this
    // new period.
    array_walk($availability, function(&$ranges) use ($end) {
        $ranges = array_filter($ranges, function($range) use($end) {
            return $range[1] > $end;
        });
    });
}

// Output the answer in the specified format.
foreach ($periods as $period) {
    echo "$period[0] -> $period[1]\n";
}
/**
 * Output:
 * 
 * 2016-04-30 12:00 -> 2016-04-30 13:31
 * 2016-04-30 15:26 -> 2016-05-01 03:00
 */

Answer 3

A different approach to your question is to use bitwise operators. The benefits of this solution are memory usage, speed and short code. The handicap is that — in your case — we can not use php integer, because we work with large numbers (1 day in minutes is 2^24*60), so we have to use GMP Extension, that is not available by default in most php distribution. However, if you use apt-get or any other packages manager, the installation is very simple.

To better understand my approach, I will use an array with a total period of 30 minutes to simplify binary representation:

$calendar = 
[
    'p1' => [
        ['start' => '2016-04-30 12:00', 'end' => '2016-04-30 12:28']
    ],
    'p2' => [
        ['start' => '2016-04-30 12:10', 'end' => '2016-04-30 12:16'],
        ['start' => '2016-04-30 12:22', 'end' => '2016-05-01 12:30']
    ]
];

First of all, we find min and max dates of all array elements, then we init the free (time) variable with the difference in minutes between max and min. In above example (30 minutes), we obtain 2³⁰-2⁰=1,073,741,823, that is a binary with 30 ‘1’ (or with 30 bits set):

111111111111111111111111111111

Now, for each person, we create the corresponding free-time variable with the same method. For the first person is easy (we have only one time interval): the difference between start and min is 0, the difference between end and min is 28, so we have 2²⁸-2⁰=268435455, that is:

001111111111111111111111111111

At this point, we update global free time with a AND bitwise operation between global free time itself and person free time. The OR operator set bits if they are set in both compared values:

111111111111111111111111111111      global free time
001111111111111111111111111111      person free time
==============================
001111111111111111111111111111      new global free time

For the second person, we have two time intervals: we calculate each time interval with know method, then we compone global person free time using OR operator, that set bits if they are set in either first or second value:

000000000000001111110000000000      12:10 - 12:16
111111110000000000000000000000      12:22 - 12:30
==============================
111111110000001111110000000000      person total free time

Now we update global free time with the same method used for first person (AND operator):

001111111111111111111111111111      previous global free time
111111110000001111110000000000      person total free time
==============================
001111110000001111110000000000      new global free time
  └────┘      └────┘
  :28-:22     :16-:10

As you can see, at the end we have an integer with bits set only in minutes when everyone is available (you have to count starting from right). Now, you can convert back this integer to datetimes. Fortunately, GMP extension has a method to find 1/0 offset, so we can avoid to perform a for/foreach loop through all digits (that in real case are many more than 30).

---

Let's see the complete code to apply this concept to your array:

$calendar = 
[
    'p1' => [
        ['start' => '2016-04-30 12:00', 'end' => '2016-05-01 03:00']
    ],
    'p2' => [
        ['start' => '2016-04-30 03:00', 'end' => '2016-05-01 03:00']
    ],
    'p3' => [
        ['start' => '2016-04-30 03:00', 'end' => '2016-04-30 13:31'],
        ['start' => '2016-04-30 15:26', 'end' => '2016-05-01 03:00']
    ]
];

/* Get active TimeZone, then calculate min and max dates in minutes: */
$tz   = new DateTimeZone( date_default_timezone_get() );
$flat = call_user_func_array( 'array_merge', $calendar );
$min  = date_create( min( array_column( $flat, 'start' ) ) )->getTimestamp()/60;
$max  = date_create( max( array_column( $flat, 'end' ) ) )->getTimestamp()/60;

/* Init global free time (initially all-free): */
$free = gmp_sub( gmp_pow( 2, $max-$min ), gmp_pow( 2, 0 ) );

/* Process free time(s) for each person: */
foreach( $calendar as $p )
{
    $pf = gmp_init( 0 );
    foreach( $p as $time )
    {
        $start = date_create( $time['start'] )->getTimestamp()/60;
        $end   = date_create( $time['end'] )->getTimestamp()/60;
        $pf = gmp_or( $pf, gmp_sub( gmp_pow( 2, $end-$min ), gmp_pow( 2, $start-$min ) ) );
    }
    $free = gmp_and( $free, $pf );
}

$result = [];
$start = $end = 0;

/* Create resulting array: */
while( ($start = gmp_scan1( $free, $end )) >= 0 )
{
    $end = gmp_scan0( $free, $start );
    if( $end === False) $end = strlen( gmp_strval( $free, 2 ) )-1;
    $result[] =
    [
        'start' => date_create( '@'.($start+$min)*60 )->setTimezone( $tz )->format( 'Y-m-d H:i:s' ),
        'end'   => date_create( '@'.($end+$min)*60 )->setTimezone( $tz )->format( 'Y-m-d H:i:s' )
    ];
}

print_r( $result );

Output:

Array
(
    [0] => Array
        (
            [start] => 2016-04-30 12:00:00
            [end]   => 2016-04-30 13:31:00
        )
    [1] => Array
        (
            [start] => 2016-04-30 15:26:00
            [end]   => 2016-05-01 03:00:00
        )
)

3v4l.org demo

Some additional notes:

• At the start, we set $tz to current timezone: we will use it later, at the end, when we create final dates from timestamps. Dates created from timestamps are in UTC, so we have to set correct timezone.
• To retrieve initial $min and $max values in minutes, firstly we flat original array, then we retrieve min and max date using array_column.
• gmp_sub subtract second argument from first argument, gmp_pow raise number (arg 1) into power (arg 2).
• In the final while loop, we use gmp_scan1 and gmp_scan0 to retrieve each ‘111....’ interval, then we create returning array elements using gmp_scan1 position for start key and gmp_scan0 position for end key.