Beregning af den samlede mængde udstyr for et datointerval

Jeg startede med følgende SQL for at samle alle datointervaller, der krydser det givne interval:

SELECT MAX(available) - IFNULL(SUM(amountInSch), 0)
FROM Table1
LEFT JOIN Table3 USING (eqid)
LEFT JOIN Table2 USING (scheduleid)
WHERE DATE(startDate) <= '2012-08-27' AND DATE(endDate) >= '2012-08-27'
  AND endTime > '08:30' AND startTime < '12:00'
  AND eqid = 1

Violin

Dette er kun den første del. Dernæst skal du regne ud de mulige overlapninger; dette ville ikke være praktisk at gøre med SQL, så jeg vil foreslå at gøre dette i PHP.

Den generiske algoritme, jeg ville vælge, er desværre O(n**2), den lyder sådan her:

• opret en tidslinje (afgrænset af hver dag) med tid som den vandrette akse
• iter over hvert dato-/tidsinterval, og marker klokkeslættet for dets venstre og højre kant for at skabe tidssegmenter af enhver mulig permutation.
• ved at bruge segmenterne summerer du lodret for overlapninger, og du tager det daglige maksimum på tværs.

Håber det hjælper.