logo标签列表

PHP如何确定多个（n个）日期时间范围重叠的时间段？

phpdatetime
8

我很难解决以下问题：

这是一个日历程序，给定多个人的可用日期时间集合，我需要在PHP中找出每个人都可用的日期时间范围。

可用性集合：

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"

我正在寻找一个可以调用的函数，它会告诉我所有(p)人在同一时间可用的日期时间范围。

在上面的示例中，答案应为:

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

我找到了一个类似的问题和答案：Datetime -Determine whether multiple(n) datetime ranges overlap each other in R

但是我不知道那是什么语言，并且无法翻译答案中的逻辑。

3个回答
5

好了，这很有趣。可能有一种更优雅的方法来完成这个任务，但我不知道PHP是否适合。请注意，目前需要单独管理开始和结束时间以进行搜索，虽然基于可用班次计算它们将是相当简单的。

<?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;
}
我建议将时间段的开始设置为最早开始班次的前一分钟，结束时间则设置为最晚结束班次的后一分钟。 - Marco
好的。这可以很容易地更改为查找一堆x时间段内是否没有重叠的周期。 - ZalemCitizen
但是，如果考虑到最早开始班次和最晚结束班次的周期很长（比如几天、几个月），它可能会消耗资源。 - ZalemCitizen
3

这个实现存在一些漏洞，请查看注释。由于这是被接受的答案，我无法删除它。在我解决此问题之前，请使用iainn或fusion3k的非常好的答案。

实际上，并不需要使用任何日期/时间处理来解决这个问题。你可以利用这种格式的日期既按字母顺序排列，也按时间顺序排列这一事实。

我不确定这是否会使解决方案变得更简单。这种方式可能更难读懂。但是，如果性能是一个关注点，它比遍历每一分钟要快得多。

您还可以使用每个单独的数组函数（array_reduce, array_filter, array_walk, array_map）以及所有其他数组功能，这很好。

当然，因为我没有使用任何日期/时间函数，所以如果需要考虑夏令时或不同时区的用户，则可能无法正常工作。

$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
 */
非常感谢你，Matt。显然你有着卓越的头脑，虽然我需要一些时间来弄清楚它的工作原理，但它确实像魔法一样运行良好。 - Ray
@matt-raines，你能帮我看一下这个问题吗？https://dev59.com/3cPra4cB1Zd3GeqPfmlk 我在我的代码中使用了上面的代码，但是问题还没有解决。 - Divyesh Jesadiya
@DivyeshJesadiya 你说得对，确实有一个bug。while循环的退出条件不太对。我已经进行了编辑，现在应该可以工作了。 - Matt Raines
@MattRaines，我已经更新了我的问题并添加了新的bug。你可以帮我吗？ - Divyesh Jesadiya
是的，恐怕以上代码并不适用于所有情况。感谢您的测试:D但我恐怕无法在不使其变得更加复杂的情况下修复它。我建议尝试其他答案，如果有机会再次查看这个问题，我会重新处理的。我想删除这个答案，但由于它已被接受，我无法这样做。:( - Matt Raines
2

对于您的问题，另一种方法是使用位运算符。这种解决方案的好处是内存使用、速度和代码短小。缺点是，在您的情况下，我们不能使用 PHP 整数，因为我们处理大数字（1 天有 224*60 分钟），所以我们必须使用 GMP 扩展, 这在大多数 PHP 发行版中默认不可用。但是，如果您使用 apt-get 或任何其他软件包管理器，安装非常简单。

为了更好地理解我的方法，我将使用一个总时长为 30 分钟的数组来简化二进制表示：

$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']
    ]
];

首先，我们找到所有数组元素的最小和最大日期，然后用最大值和最小值之间的分钟差初始化自由（时间）变量。在上面的示例中（30分钟），我们得到2的30次方-2的0次方= 1,073,741,823，这是一个带有30个“1”的二进制（或者具有30个位设置）。
111111111111111111111111111111

现在，对于每个人，我们使用相同的方法创建相应的空闲时间变量。对于第一个人来说很容易（我们只有一个时间间隔）：开始和最小值之间的差为0，结束和最小值之间的差为28，因此我们有2的28次方减去2的0次方等于268435455，即：
001111111111111111111111111111

在这一点上，我们使用 AND 位运算符将全局空闲时间与个人空闲时间进行更新。如果在比较的值中都被设置了，则 OR 运算符会设置位： 

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

对于第二个人，我们有两个时间间隔：我们使用已知方法计算每个时间间隔，然后使用OR运算符组合全局人员空闲时间，如果它们在第一个或第二个值中设置，则设置位：
000000000000001111110000000000      12:10 - 12:16
111111110000000000000000000000      12:22 - 12:30
==============================
111111110000001111110000000000      person total free time

现在我们使用与第一人称相同的方法（AND运算符）更新全局空闲时间：

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

正如您所见，最后我们有一个整数，其中只在每个人都可以使用时设置了分钟位（您必须从右边开始计数）。现在，您可以将此整数转换回日期时间。幸运的是，GMP扩展具有查找1/0偏移量的方法，因此我们可以避免通过所有数字执行for/foreach循环（实际情况下比30多得多）。

让我们来看一下将此概念应用于您的数组的完整代码：

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

输出：

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演示

一些额外的注释：

  • 在开始时，我们将$tz设置为当前时区：我们稍后会用到它，在从时间戳创建最终日期时使用。从时间戳创建的日期是UTC时间，因此我们必须设置正确的时区。
  • 要检索以分钟为单位的初始$min和$max值，首先我们将原始数组展平，然后使用array_column检索最小和最大日期。
  • gmp_sub从第一个参数中减去第二个参数，gmp_pow将数字（arg 1）提高到幂（arg 2）。
  • 在最终的while循环中，我们使用gmp_scan1和gmp_scan0来检索每个“111....”间隔，然后使用gmp_scan1位置为start键和gmp_scan0位置为end键创建返回数组元素。
嗨，Fusion，我在一个共享的Web主机上，看起来我没有安装GMP扩展的访问权限。非常感谢您详细的回复，您显然对这方面非常了解。 - Ray
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接