Ho problemi a creare un algoritmo compatibile con mysql per questo.
Sfondo
App con mysql, perl e JS. È un sistema di prenotazione in cui ogni booking è composto da start , end e qty . L'inizio e la fine sono timestamp.
Schema semplificato in una singola tabella:
| bookings
|-------------------
| id | pkey
| start | timestamp
| end | timestamp
| qty | int
Domanda
In SQL, come controllate quante risorse sono state prenotate contemporaneamente per un dato timeRange ? Il codice con spiegazione o un algoritmo compatibile con SQL funzionano entrambi.
Quindi, per il seguente programma:
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 ----- -----
Dovrei ottenere 12 poiché le prenotazioni x2 e x10 non si sovrappongono alla prenotazione x7, quindi non ci sono mai più di 12 elementi prenotati contemporaneamente tra 9:00 e 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
Quale è questo algoritmo:
Max of
For each booking that overlaps given timeRange
return sum of
each booking that overlaps this booking and given timeRange
Nell'elenco sopra questo sarebbe:
max([7],[2+10],[10+2]) = 12
Ma dato un programma come:
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 ----- -----
Questo dà:
max([7+10],[2+10],[10+7+2]) = 19
Che è sbagliato.
L'unico modo in cui posso pensare di risolvere questo problema è usare la ricorsione (che non è un afaik compatibile con mysql).
Sembrerebbe qualcosa di simile (nel codice JS funzionante)
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));
Un modo per farlo in SQL? (qualsiasi modo ragionevole, cioè)
Aggiorna
Ho appena provato a utilizzare un metodo di emulazione ricorsiva di stored procedure come documentato qui . Ma in parte l'ho implementato, l'ho provato con i dati demo e ho deciso che la performance era troppo terribile. In realtà, aveva solo bisogno dell'indicizzazione. Ora è solo un po 'brutto.