PHP实现：基于多数组键搜索创建日期范围数组（酒店换房场景）

问题概述 #

我们需要处理酒店满房场景下的客人中途换房需求：给定按日期段存储的空闲房间数组$freeRooms，以及客人的完整预订日期范围$dateRange，要为每个日期分配一个空闲房间ID，核心要求是使用最少的房间ID（即最小化换房次数）。

输入数据 #

先明确输入的两个数组（原$freeRooms存在重复键名，已修正避免数据覆盖）：

// 修正后的空闲房间数组
$freeRooms = array(
    0 => array('2020-07-23' => 37),
    1 => array('2020-07-20' => 38, '2020-07-21' => 38, '2020-07-22' => 38),
    2 => array('2020-07-25' => 38, '2020-07-26' => 38),
    9 => array('2020-07-20' => 59, '2020-07-21' => 59),
    3 => array('2020-07-20' => 86, '2020-07-21' => 86),
    4 => array('2020-07-20' => 39, '2020-07-21' => 39),
    5 => array('2020-07-25' => 39, '2020-07-26' => 39),
    6 => array('2020-07-20' => 40),
    7 => array('2020-07-24' => 40, '2020-07-25' => 40, '2020-07-26' => 40),
    8 => array('2020-07-20' => 41, '2020-07-21' => 41, '2020-07-22' => 41, '2020-07-23' => 41)
);

$dateRange = array('2020-07-20', '2020-07-21', '2020-07-22', '2020-07-23', '2020-07-24', '2020-07-25', '2020-07-26');

实现思路 #

要实现最少换房，核心逻辑是优先选择能覆盖当前日期及最长后续连续日期的房间，具体步骤如下：

1. 将$freeRooms转换为「房间ID => 可用日期集合」的映射结构，方便快速查询每个房间的可用日期
2. 遍历$dateRange，从当前未分配的日期开始，筛选出所有在该日期可用的房间
3. 对这些房间，计算它们能覆盖的从当前日期开始的最长连续日期长度
4. 选择长度最长的房间，为这段连续日期分配该房间ID
5. 跳过已分配的日期，重复上述步骤直到所有日期完成分配

PHP代码实现 #

<?php
// 修正后的空闲房间数组
$freeRooms = array(
    0 => array('2020-07-23' => 37),
    1 => array('2020-07-20' => 38, '2020-07-21' => 38, '2020-07-22' => 38),
    2 => array('2020-07-25' => 38, '2020-07-26' => 38),
    9 => array('2020-07-20' => 59, '2020-07-21' => 59),
    3 => array('2020-07-20' => 86, '2020-07-21' => 86),
    4 => array('2020-07-20' => 39, '2020-07-21' => 39),
    5 => array('2020-07-25' => 39, '2020-07-26' => 39),
    6 => array('2020-07-20' => 40),
    7 => array('2020-07-24' => 40, '2020-07-25' => 40, '2020-07-26' => 40),
    8 => array('2020-07-20' => 41, '2020-07-21' => 41, '2020-07-22' => 41, '2020-07-23' => 41)
);

$dateRange = array('2020-07-20', '2020-07-21', '2020-07-22', '2020-07-23', '2020-07-24', '2020-07-25', '2020-07-26');

// 步骤1：转换为房间ID => 可用日期集合的结构
$roomAvailableDates = [];
foreach ($freeRooms as $dateSegment) {
    foreach ($dateSegment as $date => $roomId) {
        if (!isset($roomAvailableDates[$roomId])) {
            $roomAvailableDates[$roomId] = [];
        }
        $roomAvailableDates[$roomId][] = $date;
        // 去重并排序，方便后续判断连续日期
        $roomAvailableDates[$roomId] = array_unique($roomAvailableDates[$roomId]);
        sort($roomAvailableDates[$roomId]);
    }
}

// 步骤2：初始化最终数组和当前处理的日期索引
$finalArray = [];
$currentIndex = 0;
$totalDates = count($dateRange);

while ($currentIndex < $totalDates) {
    $currentDate = $dateRange[$currentIndex];
    $bestRoomId = null;
    $maxContinuousDays = 0;

    // 筛选当前日期可用的房间
    $availableRooms = [];
    foreach ($roomAvailableDates as $roomId => $dates) {
        if (in_array($currentDate, $dates)) {
            $availableRooms[] = $roomId;
        }
    }

    // 计算每个可用房间能覆盖的最长连续天数
    foreach ($availableRooms as $roomId) {
        $roomDates = $roomAvailableDates[$roomId];
        $continuousDays = 0;
        $tempIndex = $currentIndex;

        while ($tempIndex < $totalDates) {
            $checkDate = $dateRange[$tempIndex];
            if (in_array($checkDate, $roomDates)) {
                $continuousDays++;
                $tempIndex++;
            } else {
                break;
            }
        }

        // 更新最优房间（优先选连续天数最长的）
        if ($continuousDays > $maxContinuousDays) {
            $maxContinuousDays = $continuousDays;
            $bestRoomId = $roomId;
        }
    }

    // 为这段连续日期分配最优房间
    for ($i = $currentIndex; $i < $currentIndex + $maxContinuousDays; $i++) {
        $finalArray[$dateRange[$i]] = $bestRoomId;
    }

    // 跳过已分配的日期，处理下一段
    $currentIndex += $maxContinuousDays;
}

// 输出结果
echo "<pre>";
print_r($finalArray);
echo "</pre>";
?>

代码说明 #

1. 房间结构转换：把原始按日期段存储的数组，转换为以房间ID为键的可用日期集合，排序后便于快速判断连续可用日期。
2. 最优房间选择：在每个未分配的起始日期，筛选可用房间并计算其能覆盖的连续日期长度，选择最长的那个，最大化减少换房次数。
3. 批量分配：确定最优房间后，直接为这段连续日期分配该房间ID，然后跳到下一个未分配日期继续处理。

运行结果 #

运行代码后会得到符合要求的结果：

Array
(
    [2020-07-20] => 41
    [2020-07-21] => 41
    [2020-07-22] => 41
    [2020-07-23] => 41
    [2020-07-24] => 40
    [2020-07-25] => 40
    [2020-07-26] => 40
)

内容的提问来源于stack exchange，提问作者user3223050