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
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:
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 :)
Create a list of available times. Each entry has a start time and an end time. Start with one entry that runs from the beginning to the end of time. Read used times from the database. If one falls at the start or end of an existing entry, shorten it appropriately. If it falls in the middle, you've got to shorten one and add a new one (to cover the same time but with a gap in the middle). This gets you away from having to look at 15 minute slots on hours-long events. And it'll still work if your slots become 5 minutes instead of 15.
Once you've read the DB, you have all the free periods in one chronological list. You might want to put them in a separate list sorted by size, as well.
A linked list might be the most logical choice, as you'll be accessing it mostly sequentially. It allows for quick adds and removes. An array of some sort ought to be slower, but arrays are very fast these days and would also allow binary searches. For really heavy usage, some sort of tree-based (for sorted sequential access) dictionary or map would give you the best of both worlds (fast adds and removes and random access). I think in this case I'd go with some sort of array.
This is a bit of work, but it could give you some real speed.