Größte Menge von parallelen Zeiträumen in einem Zeitraum ermitteln

[Getox]

Hallo,

ich muss ein Problem lösen, wo ich auf keine schöne Lösung komme. Ich schiebe das jetzt schon seit Wochen vor mir her, denke zwischendurch drüber nach und schiebe es wieder nach hinten.

Ich habe einen Terminkalender. Dort will ich einen Termin anlegen. Es können aber nur X Termine gleichzeitig stattfinden, wobei X ziemlich variabel sein kann. Jetzt muss ich prüfen ob in dem Zeitraum des neuen Termins zu irgendeinem Zeitpunkt bereits X Termine zeitgleich laufen. ist dem nicht so, darf der neue Termin angelegt werden und sonst nicht.

Bei zwei Zeiträumen ist so eine Überprüfung ja noch einfach. Aber bei 3, 4 oder noch mehr Terminen, die zur gleichen Zeit stattfinden dürfen, ist das irgendwie schwerer :(

Danke :)

[Papaschlumpf73]

Es geht bestimmt auch eleganter… Ich würde eine Schleife erstellen, die vom Startzeitpunkt bis zum Endzeitpunkt des neuen Termins durchläuft. Wenn es sich um ganz normale Termine handelt, würden wohl Minutenschritte ausreichen. Dann würde ich bei jedem Schritt prüfen, wie viele Termine in dieser Minute stattfinden.

[Medium]

Eventuell auch "schmutzig" numerisch lösbar, wenn man voraussetzen kann, dass ein Termin garantiert eine gewisse Länge nicht überschreitet: (Ich gehe mal davon aus, dass ein Termin durch Start- und Endzeitpunkt definiert wurde.)

Vom neuen Terminzeitpunkt ausgehend die maximale Termindauer zurückrechnen, und von da an alle Termine bis zum neuen durchgehen. Wenn ein Termin anfängt einen Zähler erhöhen, wenn einer endet einen weiteren Zähler erhöhen - dieser kann aber niemals größer als der dann gerade aktuelle Start-Zähler sein (passiert wenn man End-Zeiten von Terminen erreicht, die zum Durchlaufanfangszeitpunkt schon liefen.) Diesen also begrenzen.
Die Differenz der zwei Zähler ist dann die Anzahl der aktiven Termine zum Zeitpunkt des neuen Termins.

Man kann noch weiter gehen, denn es könnten ja Termine SPÄTER anfangen als der neue, und der neue würde dann das Limit sprengen, wenn der neue dann noch läuft. Daher also das obige bis zum ENDE des neuen Termins laufen lassen, und wenn die Differenz in diesem Schritt jemals größer wird als die maximale Terminanzahl, dann ist der Zeitraum abzuweisen.

Das zumindest wäre mein ad hoc Gedanke dazu.

Einzige Hürde: Man muss die Termin-Start- und Endzeitpunkte des Suchzeitraums in eine gemeinsame chronologische Liste bringen, und dort auch markieren was ein Start- und was ein Endpunkt ist. Das sollte sich aber relativ einfach machen lassen und kostet auch nicht arg viel Rechenleistung.

[MyRealName]

Kannst du denn nicht alles in eine Tabelle schreiben und dann einfach mit SQL fgragen, welche überlappend sind und wieviele es gibt ? Da kommt es dann drauf an, wie du überlappened definierst, reicht es, wenn das Enddatum des einen Termins im Bereich des neuen Termins ist ?

Code:

SELECT * FROM Termine WHERE (Startdate BETWEEN :NewStartDate AND :NewEndDate) -- Alle die im neuen Terminbereich auch anfangen
                         OR (Enddate BETWEEN :NewStartDate AND :NewEndDate)   -- Alle die im neuen Bereich aufhöhren
                         OR (:NewStartDate BETWEEN StartDate AND EndDate)     -- Alle wo der anfang des neuen zwischen start und ende eines vorhanden ist

Denke mal, das sollte alles abdecken

Wenn du da noch einen "Select Count()" drumherum machst, weisst, wieviele bei rumkommen :)

[Uwe Raabe]

Zitat:

Zitat von MyRealName (Beitrag 1412356)

Denke mal, das sollte alles abdecken

Leider nicht. Nehmen wir folgendes Beispiel:

Termin A geht von 8:00 - 10:00
Termin B geht von 10:00 - 12:00

Der neue Termin C geht von 9:00 - 11:00 und es sind maximal zwei überlappende Termine erlaubt. Die simple Range-Betrachtung liefert zwei überlappende Termine mit C, aber immer nur einer (A oder B) fällt auf einen beliebigen Zeitpunkt vom C-Bereich.

[Delphi.Narium]

Der Ansatz von MyRealName ist schon richtig. Man darf aber nicht die Gesamtsumme der Überschneidungen zählen, sondern muss dies für Beginn und Ende separat.

Hat man dann für den Beginn oder für das Ende mehr als die maximal zulässigen Überschneidungen, dann gehts nicht. Sonst schon.

Nur hingedaddelt und nicht getestet:

SQL-Code:

select Sum(Start) as Start, Sum(End) As End from (
  select count(*) as Start, 0 As End from Termine 
  where StartDate between :NewStartDate and :NewEndDate
  union all
  select 0 as Start, Count(*) As End from Termine 
  where EndDate between :NewStartDate and :NewEndDate
)

Wenn nun Start >= maximale Terminzahl ist oder End >= maximale Terminzahl ist, muss die Terminablage abgelehnt werden. Andernfalls müsste es gehen (sofern ich da jetzt keinen Denkfehler gemacht gabe, was ich nicht ausschließen will).

Bei dem Beispiel von Uwe Raabe müsste eine Terminanlage erfolgen können.

[Uwe Raabe]

Zitat:

Zitat von Delphi.Narium (Beitrag 1412360)

Der Ansatz von MyRealName ist schon richtig. Man darf aber nicht die Gesamtsumme der Überschneidungen zählen, sondern muss dies für Beginn und Ende separat.

Hat man dann für den Beginn oder für das Ende mehr als die maximal zulässigen Überschneidungen, dann gehts nicht. Sonst schon.
...
Wenn nun Start >= maximale Terminzahl ist oder End >= maximale Terminzahl ist, muss die Terminablage abgelehnt werden. Andernfalls müsste es gehen (sofern ich da jetzt keinen Denkfehler gemacht gabe, was ich nicht ausschließen will).

Termin A geht von 8:00 - 9:30
Termin B geht von 9:45 - 10:15
Termin C geht von 10:30 - 12:00

Neuer Termin von 9:00 - 11:00

Die Abfrage ergibt für den neuen Terminzeitraum 2x Start und 2x End.

[Delphi.Narium]

ok, erwischt.

War wohl deutlich zu kurz gesprungen ;-(

[TigerLilly]

Ich würde eine Liste aller Termine an dem Tag des neuen Termins erstellen + für jeden prüfen, ob er mit dem neuen Termin überlappt.
Überlappen kann sein:
- bestehender Termin beginnt nach, aber vor dem Ende des neuen Termins
- bestehender Termin endet nach dem Beginn, aber vor dem Ende des neuen Termins
- bestehender Termin beginnt vor und endet nach dem neuen Termin

Die Überlappungen werden mitgezählt. ist das Ergebnis < X --> zulassen.

Wenn die Termine über mehrere Tage gehen können, wird das Erstellen der Liste etwas aufwändiger, aber die Idee bleibt die gleiche.

[hoika]

Hallo,
ich hatte das damals umgedreht, nicht auf Überlappung testen, sondern auf Nichtüberlappung.
S1, E1, S2, E2 (S=Start, E=Ende)

Termin2 überlappt nicht mit Termin1, wenn er davor liegt (E2<=S1) oder dahinterliegt (S2>=E1).