Idee/Ansatz für Termin-Buchungssystem gesucht.

[Michael Schröpl]

Hi Elya,

Dies soll eine gewisse Flexibilität für den Anbieter der DL gewährleisten (er kann schieben, wenn der Kunde ihm mehr als n Stunden gibt), kompliziert aber die Programmierung.

in der Tat. Dein Szenario ist äquivalent zu einer verschäften Form des Knapsack-Problems, und das allein ist immerhin schon NP-vollständig ...

Aber wie kann ich prüfen, ob für den angegebenen Zeitraum noch ein Termin "oben drauf" zu packen ist?

Indem Du es ausprobierst. Und ich fürchte, das bedeutet, Permutationen zu generieren und den Rekursionsbaum überall dort abzuschneiden, wo Du eine Kollision findest ("Suche in der Tiefe").
Je effizienter Du diesen Baum beschneidest, desto schneller wird Dein Algorithmus werden; zunächst mußt Du den Baum (über alle möglichen Reihenfolgen Deiner Ereignisse) aber überhaupt mal generieren, und das ist m. E. schon das Hauptproblem.

Ich hatte schon einmal gedacht, daß man die Termin-Tabelle von hinten (Y = Endzeitpunkt) füllt, komme da aber nicht weiter.

Gäbe es einen linearen Algorithmus für das allgemeine Problem, dann wäre dieser ungefähr einen Nobelpreis wert. ;-)

Ich rate Dir davon ab, das Probieren innerhalb des CGI-Timeout zu realisieren ... mach es lieber im Hintergrund und generiere eine Bestätigungs- oder Ablehnungs-E-Mail an den Besucher.

Du kannst aufgrund Deines Datenbestandes immerhin feststellen, ob Dein Problem leicht ist oder schwer, indem Du einen trivialen Versuch unternimmst (z. B.: Sortiere alle Ereignisse nach ihrem Intervall-Mittelpunkt und fülle sie sequentiell in Dein Zeitraster - bei dünn besetzten Ereignismengen wird das oft funktionieren). In diesem Falle kannst Du dem Besucher die Annahme sofort bestätigen.
Falls dies jedoch scheitert, müßte ein intelligenterer Ansatz verwendet werden, und der kann dann dauern ...

Viele Grüße
      Michael