算法：合并日期范围

Question

我正在尝试找到将日期范围合并为一个数据库记录（数组元素）的最佳方法。

这是我的数据：

  Array
(
    [0] => Array
        (
            [id] => 18298
            [start_date] => 2011-07-09
            [end_date] => 2011-10-01
        )

    [1] => Array
        (
            [id] => 18297
            [start_date] => 2011-06-01
            [end_date] => 2011-06-30
        )

    [2] => Array
        (
            [id] => 17113
            [start_date] => 2011-03-31
            [end_date] => 2011-05-31
        )

    [3] => Array
        (
            [id] => 20555
            [start_date] => 2011-01-03
            [end_date] => 2011-03-31
        )
)

"在我们将它们组合之后，数组（或数据库）应该是这样的："

Array
(
    [0] => Array
        (
            [merged_ids] => 18298
            [start_date] => 2011-07-09
            [end_date] => 2011-10-01
        )

    [1] => Array
        (
            [merged_ids] => 18297, 17113, 20555
            [start_date] => 2011-01-03
            [end_date] => 2011-06-30
        )
)

有没有一种算法可以遍历所有元素/范围并将它们组合起来？哪种方法更好/更容易 - 通过数据库（MYSQL）还是编码（PHP）？

非常感谢任何建议。

谢谢！

更新：对不起，我没有提供足够的信息：我们应该合并任何连续且重叠的日期范围。

- Kelvin

---

你如何确定哪些日期应该合并？是因为它们是连续的吗？ - Argote

原日期范围不会重叠，这点有保证吗？ - Alnitak

在他给出的示例数据中，20555和17113是否重叠？此外，merged_ids属性的元素是否有任何排序方式？ - Argote

@Alnitak和@Argote，我们应该合并任何连续且重叠的日期范围。 - Kelvin

Answer 1

按开始日期排序。

然后遍历并检查下一个项目的开始日期是否在当前项目的结束日期之前或直接之后。如果是，则将下一个项目合并到当前项目中。然后继续。

- Amber

---

你好@Amber，感谢你的回答。我忘了提到日期范围可能会重叠。这些也应该合并。 - Kelvin

@Kelvin - 这很简单 - 只需检查并查看下一个日期范围的结束日期是否在当前日期范围的结束日期之前。 - Amber

@Kelvin - 实际上，你甚至不需要这样做 - 因为如果结束日期在当前日期之前，则开始日期也肯定在当前日期之前，因此我描述的原始检查也会捕获它。 - Amber

以下是处理该逻辑的 PHP 代码：http://mdb-blog.blogspot.com/2020/12/php-merge-dateranges-algorithm.html - mr.baby123

这个合并逻辑的PHP代码可以在这里找到：http://mdb-blog.blogspot.com/2020/12/php-merge-dateranges-algorithm.html - mr.baby123

Answer 2

我的方法将生成一个合并的数组，其中重叠或连续的日期被分组在一起，并且组的ID以逗号空格分隔的字符串形式存储。

我正在使用现代的“太空船运算符”（<=>）进行usort()比较。如果您的代码运行在php7以下版本上，您可以使用：

usort($array,function($a,$b){ return strcmp($a['start_date'],$b['start_date']); });

请查看内联注释以获得逐步说明。

代码：(演示)

function mergeRanges($array){
    usort($array,function($a,$b){ return $a['start_date']<=>$b['start_date']; });  // order by start_date ASC

    foreach($array as $i=>$row){
         if($i && $row['start_date']<=date('Y-m-d',strtotime("{$result[$x]['end_date']} +1 day"))){  // not the first iteration and dates are within current group's range
            if($row['end_date']>$result[$x]['end_date']){  // only if current end_date is greater than existing end_date
                $result[$x]['end_date']=$row['end_date'];  // overwrite end_date with new end_date in group
            }
            $result[$x]['merged_ids'][]=$row['id'];  // append id to merged_ids subarray
        }else{  // first iteration or out of range; start new group
            if($i){  // if not first iteration
                $result[$x]['merged_ids']=implode(', ',$result[$x]['merged_ids']);  // convert previous group's id elements to csv string
            }else{  // first iteration
                $x=-1;  // declare $x as -1 so that it becomes 0 when incremented with ++$x
            }
            $result[++$x]=['merged_ids'=>[$row['id']],'start_date'=>$row['start_date'],'end_date'=>$row['end_date']]; // declare new group
        }
    }
    $result[$x]['merged_ids']=implode(', ',$result[$x]['merged_ids']);  // convert final merged_ids subarray to csv string
    return $result;
}

$array=[
    ['id'=>18298,'start_date'=>'2011-07-09','end_date'=>'2011-10-01'],
    ['id'=>18297,'start_date'=>'2011-06-01','end_date'=>'2011-06-30'],
    ['id'=>17113,'start_date'=>'2011-03-31','end_date'=>'2011-05-31'],  // tests that 17113 and 18297 belong in same group
    ['id'=>20556,'start_date'=>'2011-02-03','end_date'=>'2011-02-13'],  // tests that "fully overlapped" date range is included
    ['id'=>20555,'start_date'=>'2011-01-03','end_date'=>'2011-03-31']
];

print_r(mergeRanges($array));

输出：

Array
(
    [0] => Array
        (
            [merged_ids] => 20555, 20556, 17113, 18297
            [start_date] => 2011-01-03
            [end_date] => 2011-06-30
        )

    [1] => Array
        (
            [merged_ids] => 18298
            [start_date] => 2011-07-09
            [end_date] => 2011-10-01
        )

)

- mickmackusa

Answer 3

我已经编写了一个函数，可以合并列表范围。它用Python编写，但应该很容易重写为PHP。这是完整的代码：https://gist.github.com/barszczmm/8447665，这是简化后的算法（仍然使用Python）：

list_of_ranges.sort() # sort input list
new_list_of_ranges = [] # output list

new_range_item_start = None
new_range_item_end = None

length = len(list_of_ranges)
for i, range_item in enumerate(list_of_ranges):
    if new_range_item_start is None:
        new_range_item_start = range_item[0]
        new_range_item_end = range_item[1]
    elif new_range_item_end >= range_item[0]:
        new_range_item_end = max(range_item[1], new_range_item_end)
    else:
        new_list_of_ranges.append((new_range_item_start, new_range_item_end))
        new_range_item_start = range_item[0]
        new_range_item_end = range_item[1]
    # save if this is last item
    if i + 1 == length:
        new_list_of_ranges.append((new_range_item_start, new_range_item_end))

- barszczmm

Answer 4

实现方式如下：

function mergeDateTimeRanges($ranges)
{
    $retVal = [];
    //sort date ranges by begin time
    usort($ranges, function ($a, $b) {
        return strcmp($a['begin_at'], $b['begin_at']);
    });

    $currentRange = [];
    foreach ($ranges as $range) {
        // bypass invalid value
        if ($range['begin_at'] >= $range['end_at']) {
            continue;
        }
        //fill in the first element
        if (empty($currentRange)) {
            $currentRange = $range;
            continue;
        }

        if ($currentRange['end_at'] < $range['begin_at']) {
            $retVal[] = $currentRange;
            $currentRange = $range;
        } elseif ($currentRange['end_at'] < $range['end_at']) {
            $currentRange ['end_at'] = $range['end_at'];
        }
    }

    if ($currentRange) {
        $retVal[] = $currentRange;
    }

    return $retVal;
}

- Bo Lu

---

此答案未提供预期输出。 - mickmackusa