PHP场景下计算日历首个可插入指定时长事件的可用时隙的库或算法有哪些？

低学习成本成熟算法 #

该场景属于典型的区间空隙查找问题，不需要掌握CPU调度相关底层知识，仅需简单的排序遍历即可实现，时间复杂度为O(nlogn)，远优于暴力逐段校验的方案，实现步骤如下：

• 先将所有已有的事件按照StartDateTime从小到大排序
• 定义你需要查找的时间范围（比如未来7天、当月等，避免无限查找）
• 优先校验查找起始时间到第一个事件开始时间的间隔，若间隔大于等于待插入事件时长，该时间段就是首个可用时隙
• 遍历排序后的事件，校验前一个事件的结束时间到下一个事件的开始时间的间隔，找到第一个符合时长要求的间隙即可
• 所有现有事件遍历完成后，校验最后一个事件结束时间到查找结束时间的间隔，符合要求则为可用时隙
• 若以上位置都没有符合要求的间隙，说明目标时间范围内无可用时隙

适配场景的PHP库 #

无需自己手动实现时间边界、时区、重叠区间等逻辑的处理，可以直接使用成熟的时间区间处理库：

• spatie/period：通用PHP时间区间处理库，原生支持区间重叠判断、空隙查找、区间合并等能力，适配所有PHP开发场景
• ryangjchandler/laravel-calendar-events：若使用Laravel框架开发可以选用，直接与Eloquent模型集成，简化日历事件相关操作

代码示例 #

原生PHP实现示例 #

/**
 * 查找首个可用的日历时隙
 * @param array $events 现有事件列表，每个元素包含StartDateTime、EndDateTime两个DateTime对象属性
 * @param DateInterval $requiredDuration 待插入事件的时长
 * @param DateTime $searchStart 查找范围的起始时间
 * @param DateTime $searchEnd 查找范围的结束时间
 * @return DateTime|null 首个可用时隙的开始时间，无可用时隙返回null
 */
function findFirstAvailableSlot(array $events, DateInterval $requiredDuration, DateTime $searchStart, DateTime $searchEnd): ?DateTime
{
    // 按事件开始时间排序
    usort($events, fn($a, $b) => $a->StartDateTime <=> $b->StartDateTime);

    $eventCount = count($events);
    // 无任何现有事件，直接返回查找起始时间
    if ($eventCount === 0) {
        return (clone $searchStart);
    }

    // 计算所需时长的总秒数
    $requiredSeconds = $requiredDuration->s + $requiredDuration->i * 60 + $requiredDuration->h * 3600 + $requiredDuration->d * 86400;

    // 校验查找起始到第一个事件的空隙
    $firstEventStart = $events[0]->StartDateTime;
    $gap = $firstEventStart->getTimestamp() - $searchStart->getTimestamp();
    if ($gap >= $requiredSeconds) {
        return (clone $searchStart);
    }

    // 校验事件之间的空隙
    for ($i = 1; $i < $eventCount; $i++) {
        $prevEnd = $events[$i-1]->EndDateTime;
        $currentStart = $events[$i]->StartDateTime;
        $gap = $currentStart->getTimestamp() - $prevEnd->getTimestamp();
        if ($gap >= $requiredSeconds) {
            return (clone $prevEnd);
        }
    }

    // 校验最后一个事件到查找结束的空隙
    $lastEventEnd = $events[$eventCount - 1]->EndDateTime;
    $gap = $searchEnd->getTimestamp() - $lastEventEnd->getTimestamp();
    if ($gap >= $requiredSeconds) {
        return (clone $lastEventEnd);
    }

    return null;
}

spatie/period 库实现示例 #

use Spatie\Period\Period;
use Spatie\Period\PeriodCollection;

// 初始化已有事件的区间集合
$periods = new PeriodCollection();
foreach ($events as $event) {
    $periods->add(Period::make($event->StartDateTime, $event->EndDateTime));
}

// 合并重叠的事件区间，避免重复判断
$periods = $periods->union();

// 定义查找范围和所需时长
$searchRange = Period::make('2024-01-01 00:00:00', '2024-01-07 23:59:59');
$requiredDuration = new DateInterval('PT2H'); // 示例为2小时时长
$requiredSeconds = $requiredDuration->s + $requiredDuration->i * 60 + $requiredDuration->h * 3600 + $requiredDuration->d * 86400;

// 获取所有空隙并查找第一个符合要求的时隙
$firstSlot = null;
foreach ($periods->gaps($searchRange) as $gap) {
    if ($gap->length() >= $requiredSeconds) {
        $firstSlot = $gap->start();
        break;
    }
}

注意事项 #

• 所有时间对象需统一时区，避免时间比对出错
• 若允许待插入事件的开始时间为整点/半点等对齐规则，可以对返回的时隙开始时间做额外的对齐处理

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