从具有重叠的 date/time 个范围数组中排除 date/time 个范围

Question

希望你一切顺利！！

我有点受困于此，我所做的只有在没有重叠的情况下才有效，无论如何我不确定这是正确的方法。

所以我当前的实现是合并所有时间（start_time 和 end_time 作为该数组中的不同条目），对它们进行排序并删除重复项（如果有）。

然后我循环进入该列表并检查每个列表是否在 $times 范围内而不在限制范围内。

所有通过这些条件的都被添加到另一个列表中。最后，我将循环遍历该列表“一次 2 项”并构建最终的时间范围数组。

代码：https://3v4l.org/2elDs（Laravel，使用 Collection 和 Carbon，因此运行不会出现）

没有 date/time 重叠的样本：

$times = [
        [
            'start_time' => '2017-06-26 00:00:00',
            'end_time' => '2017-06-26 05:00:00',
        ],
        [
            'start_time' => '2017-06-26 13:00:00',
            'end_time' => '2017-06-26 18:00:00',
        ]
    ];

$timesToExclude= [
        [
            'start_time' => '2017-06-26 04:00:00',
            'end_time' => '2017-06-26 04:30:00',
        ],
        [
            'start_time' => '2017-06-26 07:00:00',
            'end_time' => '2017-06-26 10:00:00',
        ],
        [
            'start_time' => '2017-06-26 15:00:00',
            'end_time' => '2017-06-26 16:00:00',
        ]
    ];

结果为：

    $result = [
        [
            "start_time" => "2017-06-26 00:00:00",
            "end_time"   => "2017-06-26 04:00:00"
        ], [
            "start_time" => "2017-06-26 04:30:00",
            "end_time"   => "2017-06-26 05:00:00"
        ],
        [
            "start_time" => "2017-06-26 13:00:00",
            "end_time"   => "2017-06-26 15:00:00"
        ],
        [
            "start_time" => "2017-06-26 16:00:00",
            "end_time"   => "2017-06-26 18:00:00"
        ]
    ]

样本 date/time 重叠

    $times = [
        [
            'start_time' => '2017-06-26 00:00:00',
            'end_time'   => '2017-06-26 10:00:00',
        ],
        [
            'start_time' => '2017-06-26 05:00:00',
            'end_time'   => '2017-06-26 20:00:00',
        ]
    ];

    $timesToExclude= [
        [
            'start_time' => '2017-06-26 04:00:00',
            'end_time'   => '2017-06-26 04:30:00',
        ],
        [
            'start_time' => '2017-06-26 07:00:00',
            'end_time'   => '2017-06-26 09:00:00',
        ],
        [
            'start_time' => '2017-06-26 15:00:00',
            'end_time'   => '2017-06-26 16:00:00',
        ]
    ];

结果应为：

$result = [
        [
            "start_time" => "2017-06-26 00:00:00",
            "end_time"   => "2017-06-26 04:00:00"
        ], [
            "start_time" => "2017-06-26 04:30:00",
            "end_time"   => "2017-06-26 05:00:00"
        ],
        [
            "start_time" => "2017-06-26 05:00:00",
            "end_time"   => "2017-06-26 07:00:00"
        ],
        [
            "start_time" => "2017-06-26 09:00:00",
            "end_time"   => "2017-06-26 10:00:00"
        ],
        [
            "start_time" => "2017-06-26 10:00:00",
            "end_time"   => "2017-06-26 15:00:00"
        ],
        [
            "start_time" => "2017-06-26 16:00:00",
            "end_time"   => "2017-06-26 20:00:00"
        ]
    ]

有人知道正确的 algo/pseudo 处理方法吗？

Answer 1

创建公共对列表 {time; flag}，其中标志为 time_start, time_end, restriction_start or restriction_end。

按时间排序此列表。如果平局使用标志作为辅助键（例如，restr_start 应该在 time_end 之后）。

制作$Active=0、$Exclude=0

遍历排序列表。

遇到time_start时，增加$Active的值{1}

遇到time_end时，$Active减值{2}

遇到restriction_start时，增加$Exclude的值{3}

遇到restriction_end时，$Exclude减值{4}

下例开启输出区间：
{1}：$Active 变为 1 且 $Exclude = 0
{4}：$Exclude becomes 0 且 $Active 非零

以下情况关闭输出区间：
{2} $Active 变为 0 且 $Exclude = 0
{3} $Exclude becomes 1 且 $Active 为非零值

示例：（不知道复杂条件的确切 php 语法）

 case $TimeStart:
            $active = $active + 1;
            if ($active=1) and ($exclude=0)
                 $range['start_time'] = $mergedTime['time'];
            break;
 ....
  case $RestrictionEnd:
            $exclude = $exclude - 1;
            if ($exclude=0) and ($active > 0)
                 $range['start_time'] = $mergedTime['time'];
            break;

Answer 2

function excludeOverlaping($disponibilities,$plages) {

        if(count($disponibilities) == 0)
            return $disponibilities;
        if(count($plages) == 0)
            return $disponibilities;

                usort($disponibilities, function($a, $b)
                {
                    return strtotime($a->startDate) - strtotime($b->startDate);
                });
                usort($plages, function($a, $b)
                {
                    return strtotime($a->startDate) - strtotime($b->startDate);
                });

                for($i = 0; $i < count($disponibilities); $i++){
                    for($j=0;$j<count($plages);$j++){
                        $dispo = $disponibilities[$i];
                        if(isset($dispo->exclude)){
                            break;
                        }
                        $plage = $plages[$j]; 
                        if(strtotime($dispo->startDate)>=strtotime($plage->startDate) && strtotime($dispo->endDate)<=strtotime($plage->endDate)){
                                $disponibilities[$i]->exclude = true;

                        }else if( strtotime($dispo->startDate)<strtotime($plage->startDate) && strtotime($dispo->endDate) <= strtotime($plage->endDate) && strtotime($dispo->endDate) > strtotime($plage->startDate)){
                                 $disponibilities[$i]->endDate = $plage->startDate;
                        }else if( strtotime($dispo->startDate)>=strtotime($plage->startDate)  && strtotime($dispo->startDate)<=strtotime($plage->endDate) && strtotime($dispo->endDate) > strtotime($plage->endDate)){
                                 $disponibilities[$i]->startDate = $plage->endDate;
                        }else if( strtotime($dispo->startDate)<strtotime($plage->startDate) &&  strtotime($dispo->endDate) > strtotime($plage->endDate) ){
                              echo "[[[4]]]\n";
                                $tmp = new stdClass();
                                $tmp->startDate = $dispo->startDate;
                                $tmp->endDate = $plage->startDate;
                                $tmp2 = new stdClass();
                                $tmp2->startDate = $plage->endDate;
                                $tmp2->endDate = $dispo->endDate;
                                $disponibilities[$i]->exclude = true;
                                array_push($disponibilities,$tmp);
                                array_push($disponibilities,$tmp2);

                        } 
                    }
                }
                for($i=0;$i<count($disponibilities);$i++){
                    if(isset($disponibilities[$i]->exclude)){
                       array_splice($disponibilities,$i,1);
                       $i--;
                    }
                }
                var_dump($disponibilities);

    }

    $times = array();
    $restrictions = array();
    $obj = new stdClass();
    $obj->startDate = '2017-06-26 00:00:00';
    $obj->endDate =  '2017-06-26 07:00:00';
    array_push($times,$obj);
    $obj = new stdClass();
    $obj->startDate = '2017-06-26 00:00:00';
    $obj->endDate = '2017-06-26 24:00:00';
    array_push($times,$obj);


    $obj = new stdClass();
    $obj->startDate =  '2017-06-26 04:00:00';
    $obj->endDate = '2017-06-26 06:00:00';
    array_push($restrictions,$obj);


    $obj = new stdClass();
    $obj->startDate = '2017-06-26 00:00:00' ;
    $obj->endDate = '2017-06-26 01:00:00';
    array_push($restrictions,$obj);


    excludeOverlaping($times,$restrictions);

从具有重叠的 date/time 个范围数组中排除 date/time 个范围

Exclude date/time ranges from an array of date/time ranges with overlapping

php

algorithm

datetime

pseudocode

range