Finding open contiguous blocks of time for every day of a month, fast
- by Chris
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.
Edit
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)
