快速为一个月中的每一天找到开放的连续时间段 - Finding open contiguous blocks of time for every day of a month, fast

我正在为一组多个场地开发预订可用性系统，并且很难生成给定月份中天数的时间段的可用性。这发生在PHP的服务器端，但这个概念本身是与语言无关的——我可以在JS或其他任何东西中这样做。

给定venue_id、月份和年份（例如 6/2012），我有一个该地点在该范围内发生的所有事件的列表，表示为 unix 时间戳start和end。此数据来自数据库。我需要确定每天存在哪些（如果有的话）最小长度（每个场地不同）的连续时间段。

例如，在 6 月 1 日，我在下午 2：00 到晚上 7：00 之间有一个活动。最短时间为 5 小时，因此那里有一个街区从上午 9 点至下午 2 点开放，另一个街区在晚上 7 点到中午 12 点之间开放。这将持续到第 2 次、第 3 次等......六月的每一天。有些（大多数）日子根本没有发生任何事情，有些则有 1 - 3 个事件。

我想出的解决方案有效，但生成数据也需要很长时间。基本上，我在每月的每一天循环，并为当天的每 15 分钟创建一个时间戳数组。然后，我将当天事件的时间跨度循环 15 分钟，将任何"采取"的时间段标记为 false。剩下的，我有一个数组，其中包含空闲时间与所用时间的时间戳：

//one day's array after processing through loops (not real timestamps)
array(
  12345678=>12345678,   // <--- avail
  12345878=>12345878,
  12346078=>12346078,
  12346278=>false,      // <--- not avail
  12346478=>false,
  12346678=>false,
  12346878=>false,
  12347078=>12347078,   // <--- avail
  12347278=>12347278
)

现在我需要循环 THIS 数组来查找连续的时间块，然后检查它们是否足够长（每个场地都有一个最小值），如果是，则为它们的开始和结束（即上午 9 点至下午 2 点）建立描述性文本。呼！当所有这些循环完成时，用户已经感到无聊并徘徊到 Youtube 观看小狗的视频;检查30天左右需要很长时间。

有没有更快的方法来解决这个问题？总结一下这个问题，给定第 d 天的时间范围 t1 和 t2，我如何确定 d 中剩余的时间比最小时间块 m 长

。

当用户在日历月之间移动时，此数据通过 AJAX 按需组装。结果是按页面加载缓存的，因此如果用户第二次转到 7 月，将重复使用第一次生成的数据。

任何其他有帮助的细节，请告诉我。

编辑

每个请求，数据库结构（或此处相关的部分）

*events*
id        (bigint)
title     (varchar)
*event_times*
id        (bigint)
event_id  (bigint)
venue_id  (bigint)
start     (bigint)
end       (bigint)
*venues*
id        (bigint)
name      (varchar)
min_block (int)
min_start (varchar)
max_start (varchar)

事件总是在 15 -- ：00，：15，：30，：45 开始

某些实际时间戳的数据转储：http://pastebin.com/k1PRkj44

这应该会让你朝着正确的方向前进（我希望）。它循环访问一段时间内（例如一个月）的数据库记录。

从该集合中，它将找到预订之间的"间隙"并填充一个数组（以日期为键）。

$days = array();
$stmt = $db->prepare('SELECT
    DATE(FROM_UNIXTIME(start)) AS sdate,
    GROUP_CONCAT(HOUR(FROM_UNIXTIME(start)),",", MINUTE(FROM_UNIXTIME(start)) ORDER BY start ASC SEPARATOR ",") AS from_hours,
    GROUP_CONCAT(HOUR(FROM_UNIXTIME(end)), ",", MINUTE(FROM_UNIXTIME(end)) ORDER BY start ASC SEPARATOR ",") AS to_hours
    FROM event_time
    WHERE start >= ? AND end < ? AND start < end
    GROUP BY sdate
    ORDER BY sdate');
$stmt->execute(array($from, $to));
foreach ($stmt->fetchAll(PDO::FETCH_ASSOC) as $row) {
    // from and to are formatted as: [hh,mm,hh,mm,hh,mm,...]
    $from = explode(',', $row['from_hours']);
    $to = explode(',', $row['to_hours']);
    // skew the two arrays:
    // - add 00:00 in the front of $to
    // - add 23:59 at the back of $from
    array_unshift($to, 0, 0);
    array_push($from, 23, 59);
    for ($i = 0, $n = count($from); $i != $n; $i += 2) {
        // create time values
        $start = new DateTime("{$to[$i]}:{$to[$i+1]}");
        $end = new DateTime("{$from[$i]}:{$from[$i+1]}");
        // calculate difference
        $diff = $start->diff($end);
        // difference must be positive and at least 5 hours apart (depending on venue)
        if (!$diff->invert && $diff->h >= 5) {
            $days[$row['sdate']][] = array($start->format('H:i'), $end->format('H:i'));
        }
    }
}

最后，$days将包含：

[2012-06-30] => Array
    (
        [0] => Array
            (
                [0] => 00:00
                [1] => 05:30
            )
        [1] => Array
            (
                [0] => 11:30
                [1] => 23:59
            )
    )

您应该更改一些变量以进行计算：

最短时间（例如，从清晨开始）
最长时间（例如，直到深夜）
最短预订时间（取决于场地）

此外，生成的数组中缺少的键在一整天都可用，因此在开始循环之前，您应该在查询期间内的所有日期开始循环之前启动$days数组。

让我知道这是否对您有帮助:)

创建可用时间列表。每个条目都有开始时间和结束时间。从一个从时间开始到结束的条目开始。从数据库中读取使用时间。如果一个落在现有条目的开头或结尾，请适当缩短它。如果它落在中间，你必须缩短一个并添加一个新的（覆盖相同的时间，但在中间有一个间隙）。这使您不必在长达数小时的活动中查看 15 分钟的时段。如果您的插槽变为 5 分钟而不是 15 分钟，它仍然有效。

阅读数据库后，您将在一个按时间顺序排列的列表中拥有所有空闲时段。您可能还希望将它们放在按大小排序的单独列表中。

链表可能是最合乎逻辑的选择，因为您将主要按顺序访问它。它允许快速添加和删除。某种数组应该更慢，但如今数组非常快，并且还允许二进制搜索。对于非常繁重的使用，某种基于树的（用于排序顺序访问）字典或映射将为您提供两全其美的效果（快速添加和删除以及随机访问）。我想在这种情况下，我会使用某种数组。

这是一些工作，但它可以给你一些真正的速度。