为一个月的每一天找到开放的连续时间块，快速

Question

I am working on a booking availability system for a group of several venues, and am having a hard time generating the availability of time blocks for days in a given month. This is happening server-side in PHP, but the concept itself is language agnostic -- I could be doing this in JS or anything else.

Given a venue_id, month, and year (6/2012 for example), I have a list of all events occurring in that range at that venue, represented as unix timestamps start and end. This data comes from the database. I need to establish what, if any, contiguous block of time of a minimum length (different per venue) exist on each day.

For example, on 6/1 I have an event between 2:00pm and 7:00pm. The minimum time is 5 hours, so there's a block open there from 9am - 2pm and another between 7pm and 12pm. This would continue for the 2nd, 3rd, etc... every day of June. Some (most) of the days have nothing happening at all, some have 1 - 3 events.

The solution I came up with works, but it also takes waaaay too long to generate the data. Basically, I loop every day of the month and create an array of timestamps for each 15 minutes of that day. Then, I loop the time spans of events from that day by 15 minutes, marking any "taken" timeslot as false. Remaining, I have an array that contains timestamp of free time vs. taken time:

//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
)

Now I would need to loop THIS array to find continuous time blocks, then check to see if they are long enough (each venue has a minimum), and if so then establish the descriptive text for their start and end (i.e. 9am - 2pm). WHEW! By the time all this looping is done, the user has grown bored and wandered off to Youtube to watch videos of puppies; it takes ages to so examine 30 or so days.

Is there a faster way to solve this issue? To summarize the problem, given time ranges t1 and t2 on day d, how can I determine the remaining time left in d that is longer than the minimum time block m.

This data is assembled on demand via AJAX as the user moves between calendar months. Results are cached per-page-load, so if the user goes to July a second time, the data that was generated the first time would be reused.

Any other details that would help, let me know.

---

Edits

Per request, the database structure (or the part that is relevant here)

*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)

Events always start on the 15 -- :00, :15, :30, :45

Data dump of some of the actual time stamps: http://pastebin.com/k1PRkj44

Answer 1

This should get you in the right direction (I hope). It iterates over the database records that fall within a period (e.g. one month).

From that set it will find the "gaps" between the bookings and fill an array (with date as key).

$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'));
        }
    }
}

At the end, $days will contain:

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

        [1] => Array
            (
                [0] => 11:30
                [1] => 23:59
            )

    )

There are a few variables that you should change to make your calculations:

1. minimum time (e.g. from how early in the morning)
2. maximum time (e.g. until how late at night)
3. minimum booking time (depending on venue)

Also, keys that are missing in the resulting array are available for the whole day, so you should prime the $days array before you start the loop with all the days within the period you're querying.

Let me know if that helped you :)