高效查找日历中第一个可用时间段的算法与实现

<?php

class Event {
    public DateTime $start;
    public DateTime $end;

    public function __construct(DateTime $start, DateTime $end) {
        $this->start = $start;
        $this->end = $end;
    }
}

?>

<?php

/**
 * 查找日历中第一个可用时间段
 *
 * @param Event[] $existingEvents 现有事件列表
 * @param int $durationMinutes 需要插入的事件时长（分钟）
 * @param DateTime $workdayStart 工作日开始时间
 * @param DateTime $workdayEnd 工作日结束时间
 * @return array|null 返回 ['start' => DateTime, 'end' => DateTime] 或 null
 */
function findFirstAvailableSlot(array $existingEvents, int $durationMinutes, DateTime $workdayStart, DateTime $workdayEnd): ?array {
    // 1. 确保事件按开始时间排序
    // 这是关键一步，保证我们能按时间顺序处理事件和间隙
    usort($existingEvents, function(Event $a, Event $b) {
        return $a->start <=> $b->start;
    });

    // 用于跟踪当前可用的时间点，初始为工作日开始时间
    $currentTime = clone $workdayStart;

    // 2. 遍历现有事件，计算可用间隙
    foreach ($existingEvents as $event) {
        // 确保当前事件在工作日范围内且不早于当前检查时间
        // 如果事件的开始时间晚于工作日结束，则后续事件也可能超出，可以直接中断
        if ($event->start >= $workdayEnd) {
            break; 
        }
        // 如果当前事件的结束时间早于或等于当前的检查点，说明此事件已被“跳过”
        // （例如，它与前一个事件重叠或完全包含在前一个事件中），直接跳过
        if ($event->end <= $currentTime) {
            continue; 
        }

        // 计算从当前检查点到当前事件开始时间之间的间隙
        $gapStart = $currentTime;
        $gapEnd = $event->start;

        // 确保间隙有效（开始时间早于结束时间）且在工作日内
        if ($gapEnd > $gapStart) {
            $interval = $gapEnd->diff($gapStart);
            $gapMinutes = $interval->days * 24 * 60 + $interval->h * 60 + $interval->i; // 计算间隙分钟数

            // 如果此间隙满足所需时长，则找到了第一个可用时间段
            if ($gapMinutes >= $durationMinutes) {
                // 计算实际可插入事件的结束时间
                $slotEnd = (clone $gapStart)->modify("+$durationMinutes minutes");
                return ['start' => $gapStart, 'end' => $slotEnd];
            }
        }

        // 更新当前检查点为当前事件的结束时间，以便计算下一个间隙
        // 使用 max() 是为了处理事件可能重叠的情况，确保 currentTime 始终向前推进
        $currentTime = max($currentTime, $event->end); 
    }

    // 3. 计算最后一个事件结束时间到工作日结束时间之间的间隙
    // 如果在循环中没有找到，检查工作日末尾的这段时间
    if ($currentTime < $workdayEnd) {
        $gapStart = $currentTime;
        $gapEnd = $workdayEnd;
        $interval = $gapEnd->diff($gapStart);
        $gapMinutes = $interval->days * 24 * 60 + $interval->h * 60 + $interval->i;

        if ($gapMinutes >= $durationMinutes) {
            $slotEnd = (clone $gapStart)->modify("+$durationMinutes minutes");
            return ['start' => $gapStart, 'end' => $slotEnd];
        }
    }

    return null; // 未找到满足条件的时间段
}

?>

<?php

// 设定工作日范围
$workdayStart = new DateTime('2023-10-27 09:00:00'); // 上午9点
$workdayEnd = new DateTime('2023-10-27 17:00:00');   // 下午5点

// 现有事件列表
$events = [
    new Event(new DateTime('2023-10-27 10:00:00'), new DateTime('2023-10-27 11:00:00')), // 事件1: 10:00 - 11:00
    new Event(new DateTime('2023-10-27 12:00:00'), new DateTime('2023-10-27 14:00:00')), // 事件2: 12:00 - 14:00
    new Event(new DateTime('2023-10-27 14:15:00'), new DateTime('2023-10-27 15:00:00')), // 事件3: 14:15 - 15:00
];

// 场景1: 查找一个60分钟的空闲时间
$requestedDuration1 = 60; 
$firstSlot1 = findFirstAvailableSlot($events, $requestedDuration1, $workdayStart, $workdayEnd);

if ($firstSlot1) {
    echo "找到第一个可用时间段 (60分钟): " . $firstSlot1['start']->format('Y-m-d H:i') . " - " . $firstSlot1['end']->format('Y-m-d H:i') . "\n";
    // 预期输出: 找到第一个可用时间段 (60分钟): 2023-10-27 09:00 - 2023-10-27 10:00
} else {
    echo "未找到满足条件的时间段 (60分钟)。\n";
}

echo "--------------------------------------------------\n";

// 场景2: 查找一个30分钟的空闲时间
$requestedDuration2 = 30;
$firstSlot2 = findFirstAvailableSlot($events, $requestedDuration2, $workdayStart, $workdayEnd);
if ($firstSlot2) {
    echo "找到第一个可用时间段 (30分钟): " . $firstSlot2['start']->format('Y-m-d H:i') . " - " . $firstSlot2['end']->format('Y-m-d H:i') . "\n";
    // 预期输出: 找到第一个可用时间段 (30分钟): 2023-10-27 09:00 - 2023-10-27 09:30
} else {
    echo "未找到满足条件的时间段 (30分钟)。\n";
}

echo "--------------------------------------------------\n";

// 场景3: 查找一个15分钟的空闲时间 (会找到 14:00 - 14:15)
$requestedDuration3 = 15;
$firstSlot3 = findFirstAvailableSlot($events, $requestedDuration3, $workdayStart, $workdayEnd);
if ($firstSlot3) {
    echo "找到第一个可用时间段 (15分钟): " . $firstSlot3['start']->format('Y-m-d H:i') . " - " . $firstSlot3['end']->format('Y-m-d H:i') . "\n";
    // 预期输出: 找到第一个可用时间段 (15分钟): 2023-10-27 14:00 - 2023-10-27 14:15
} else {
    echo "未找到满足条件的时间段 (15分钟)。\n";
}

echo "--------------------------------------------------\n";

// 场景4: 所有时间都被占用，或请求时长过长
$allDayEvents = [
    new Event(new DateTime('2023-10-27 09:00:00'), new DateTime('2023-10-27 17:00:00')), // 全天事件
];
$requestedDuration4 = 60;
$firstSlot4 = findFirstAvailableSlot($allDayEvents, $requestedDuration4, $workdayStart, $workdayEnd);
if ($firstSlot4) {
    echo "找到第一个可用时间段 (60分钟, 全天占用): " . $firstSlot4['start']->format('Y-m-d H:i') . " - " . $firstSlot4['end']->format('Y-m-d H:i') . "\n";
} else {
    echo "未找到满足条件的时间段 (60分钟, 全天占用)。\n";
    // 预期输出: 未找到满足条件的时间段 (60分钟, 全天占用)。
}

?>