I'm having trouble creating a mysql compatible algorithm for this.
Background
App with mysql, perl and JS. It's a booking system where each booking is comprised of a start, end and qty. Start and end are timestamps.
Schema simplified to a single table:
| bookings
|-------------------
| id | pkey
| start | timestamp
| end | timestamp
| qty | int
Question
In SQL, how do you check how many resources are booked at once for a given timeRange? Code with explanation or an algorithm that is SQL compatible both work.
So, for the following schedule:
09:00 ----- <-|
09:30 | | | A maximum of 12 are booked at once during this range
10:00 |x7 | |
10:30 ----- ----- ----- |
11:00 | | | | |
11:30 |x2 | |x10| <-|
12:00 | | | |
12:30 ----- -----
I should get 12 since the x2 and x10 bookings don't overlap with the x7 booking, so there are never more than 12 items booked at once between 9:00 and 11:30.
Progress
--It's been heavily shrunk to show just the relevant part, so it might have some errors
SELECT coalesce(max(qtyOverlap.sum),0) booked
FROM (
SELECT coalesce(sum(b2.qty),0) sum
FROM booking b1
LEFT JOIN (
SELECT b.qty, b.tStart, b.tEnd FROM booking b
) b2
ON b1.tStart < b2.tEnd AND
b1.tEnd > b2.tStart AND
b2.tStart < '2015-02-19 16:30:00' AND
b2.tEnd > '2015-02-19 06:00:00'
WHERE
b1.tStart < '2015-02-19 16:30:00' AND
b1.tEnd > '2015-02-19 06:00:00'
GROUP BY b1.id
) qtyOverlap
GROUP BY qtyOverlap.itemId
Which is this algorithm:
Max of
For each booking that overlaps given timeRange
return sum of
each booking that overlaps this booking and given timeRange
In the schedule above this would be:
max([7],[2+10],[10+2]) = 12
But given a schedule like:
09:00 ----- <-|
09:30 | | | A maximum of 17 are booked at once during this range, not 19
10:00 |x7 | |
10:30 | | ----- |
11:00 ----- | | |
11:30 ----- |x10| <-|
12:00 |x2 | | |
12:30 ----- -----
This gives:
max([7+10],[2+10],[10+7+2]) = 19
Which is wrong.
The only way I can think of to fix this is to use recursion (which isn't mysql compatible afaik).
It would look something like (in working JS code)
function getOverlaps(bookings,range) {
return bookings.filter(function(booking){
return isOverLapping(booking,range);
});
}
function isOverLapping(a, b) {
return (a.start < b.end && a.end > b.start);
}
function maxSum(booking, overlaps) { // main recursive function
var currentMax = 0;
var filteredOverlaps = getOverlaps(overlaps,booking);
for (var i = 0; i < filteredOverlaps.length; i++) {
currentMax = Math.max(
maxSum(filteredOverlaps[i], removeElement(filteredOverlaps,i)),
currentMax
);
}
return currentMax + booking.qty;
}
function removeElement(array,i){
var clone = array.slice(0)
clone.splice(i,1);
return clone;
}
var maxBooked = maxSum(timeRange, getOverlaps(bookings,timeRange));
Any way to do this in SQL? (any reasonable way, that is)
Update
I just tried to use a stored procedure recursion emulation method as documented here. But part way through implementing it, I tried it with the demo data and decided the performance was far too terrible. Actually, it just needed indexing. Now it's just 'kinda' bad.
