Berechnung von gleichzeitigen Zugriffen

[msickel]

Hallo liebe Delphianer,

ich bräuchte mal eure Hilfe für eine Berechnung, ich habe keine Ahnung wie ich das umsetzen kann, vielleicht kann mir jemand helfen mit einer Formel oder einem anderen Lösungsweg.

ich habe zum Beispiel eine Tabelle mit folgende Werten

Delphi-Quellcode:

time of start   time of end
31.03.2010 15:10   31.03.2010 15:34
31.03.2010 08:33   31.03.2010 09:43
30.03.2010 10:54   30.03.2010 11:01
30.03.2010 10:53   30.03.2010 11:02
30.03.2010 10:38   30.03.2010 10:52
30.03.2010 10:37   30.03.2010 10:51
30.03.2010 10:07   30.03.2010 10:36
30.03.2010 09:48   30.03.2010 09:54
26.03.2010 14:03   26.03.2010 14:24
26.03.2010 10:21   26.03.2010 11:09
25.03.2010 16:53   25.03.2010 18:03
25.03.2010 16:18   25.03.2010 16:52
25.03.2010 10:54   25.03.2010 11:26
25.03.2010 10:52   25.03.2010 10:59
25.03.2010 10:47   25.03.2010 10:51
25.03.2010 10:46   25.03.2010 11:01
25.03.2010 10:20   25.03.2010 11:00
24.03.2010 14:09   24.03.2010 14:48
24.03.2010 13:33   24.03.2010 13:48
23.03.2010 09:48   23.03.2010 10:37
22.03.2010 15:47   22.03.2010 16:09
22.03.2010 15:27   22.03.2010 15:46
22.03.2010 14:53   22.03.2010 14:59
22.03.2010 14:51   22.03.2010 14:59
22.03.2010 14:48   22.03.2010 14:50
22.03.2010 14:46   22.03.2010 14:55
22.03.2010 14:43   22.03.2010 14:46
22.03.2010 14:42   22.03.2010 14:51
22.03.2010 14:36   22.03.2010 14:46
22.03.2010 14:34   22.03.2010 14:42
22.03.2010 14:34   22.03.2010 14:40
22.03.2010 14:34   22.03.2010 14:37
22.03.2010 14:13   22.03.2010 14:33

wie kann ich nun den höchsten Wert der gleichzeitigen Zeitüberschneidungen pro Tag herausfinden?

Martin

[Codewalker]

Muss du das nur einmalig machen? Und brauchst du es in Delphi oder reicht das Ergebnis? In letzterem Fall würde ich vermutlich Excel bemühen, da dürfte das in weniger als 10 Minuten erledigt sein.

[Hubi89]

Heyho,

ich hab mir mal Folgendes überlegt und denke das könnte funzen:

Du erstellt ein Array der Länge 24 * 60 = 1440 (also für jede Minute des Tages). Dann schreibst du für jeden Wert (wie zb 30.03.2010 10:07 - 30.03.2010 10:36 ) in das Feld für die Uhrzeit (hier: 10:07, also 10 * 60 + 7 = 67 (oder so)) die Dauer des Vorgangs, also hier 29. Danach gehst du für jedes nicht-leere Feld jeweils k Werte in die Zukunft. Hierbei steht k für den Wert, der in dem aktuellen Feld steht (bei 247 wäre k = 29). Allerdings verringerst du mit jedem Feld, das du weiter gehst k um 1 (also dec(k)^^). Wenn du jetzt auf ein nicht-leeres Feld stößt (sagen wir mit dem Wert p), heißt das, dass eine Überschneidung stattfindet. Die Überschneidungslänge findest du, indem du den aktuellen k Wert und den aufgefundenen Wert p vergleichst. Wenn p > k, so ist die Überschneidungslänge k, wenn k > p so, ist die Überschneidungslänge p, also Überschneidungslänge = min(k,p). Den aktuellen Maximalwert speicherst du immer. Wenn du bei allen Werten durchgelaufen bist, bist du fertig und hast die größte Überschneidung. Ich sollte noch erwähnen, dass wenn k viel größer als p ist, kann es vorkommen, dass du nach dem ersten Auftreffen auf eine Überscheidung danach noch eine größere finden kannst, also k unbedingt bis 0 gehen lassen.

Gruß
Katja

[s.h.a.r.k]

Ich habe jetzt doch auch noch eine Idee, die ähnlich zu der meiner Vorrednerin ist. Man spanne für jeden Tag ein Array auf mit 24 * 60 = 1440 Werten. Für jede Minute einer Zeitspanne inkrementiere man das Array an entsprechender Stelle um 1. Beispiel:

Code:

15:10 -> 15 * 60 + 10 = 370 -> Array[370] := Array[370] + 1
15:11 -> 15 * 60 + 11 = 371 -> Array[371] := Array[371] + 1

usw.

15:36 -> 15 * 60 + 36 = 396 -> Array[396] := Array[396] + 1

In einem zweiten Schritt berechne ich das Maximum des Arrays und speichere dessen erstes Auftreten, d.h. den Index im Array. Ist das Maximum 1, so kann ich abbrechen, da es keine Überlappung an diesem Tag gibt. Ist diese jedoch größer als 1, so springe ich zum gespeicherten Index und gehe davon ausgehend immer weiter (Index + 1) bis ich einen Wert finde, der kleiner als der Maximalwert ist. Somit erhalte ich die Überlappungsdauer in Minuten.

// edit

Wenn du folgendes suchst, dann ist meine Idee falsch:

Code:

max { Menge der paarweise Zeitüberschneidungen }

[Blup]

Die Daten erst einmal umformen und sortieren nach Datum/Uhrzeit.
Dann eine Schleife über alle Datensätze, die eine Variable bei jedem "start" erhöht und jedem "end" verringert und den temporär größten Wert merken.

Code:

22.03.2010 14:13   start
22.03.2010 14:33   end
22.03.2010 14:34   start
22.03.2010 14:34   start
22.03.2010 14:34   start
22.03.2010 14:36   start
22.03.2010 14:37   end
22.03.2010 14:40   end
22.03.2010 14:42   start
22.03.2010 14:42   end
22.03.2010 14:43   start
22.03.2010 14:46   start
22.03.2010 14:46   end
22.03.2010 14:46   end
22.03.2010 14:48   start
22.03.2010 14:50   end
22.03.2010 14:51   start
22.03.2010 14:51   end
22.03.2010 14:53   start
22.03.2010 14:55   end
22.03.2010 14:59   end
22.03.2010 14:59   end
22.03.2010 15:27   start
22.03.2010 15:46   end
22.03.2010 15:47   start
22.03.2010 16:09   end
23.03.2010 09:48   start
23.03.2010 10:37   end
24.03.2010 13:33   start
24.03.2010 13:48   end
24.03.2010 14:09   start
24.03.2010 14:48   end
25.03.2010 10:20   start
25.03.2010 10:46   start
25.03.2010 10:47   start
25.03.2010 10:51   end
25.03.2010 10:52   start
25.03.2010 10:54   start
25.03.2010 10:59   end
25.03.2010 11:00   end
25.03.2010 11:01   end
25.03.2010 11:26   end
25.03.2010 16:18   start
25.03.2010 16:52   end
25.03.2010 16:53   start
25.03.2010 18:03   end
26.03.2010 10:21   start
26.03.2010 11:09   end
26.03.2010 14:03   start
26.03.2010 14:24   end
30.03.2010 09:48   start
30.03.2010 09:54   end
30.03.2010 10:07   start
30.03.2010 10:36   end
30.03.2010 10:37   start
30.03.2010 10:38   start
30.03.2010 10:51   end
30.03.2010 10:52   end
30.03.2010 10:53   start
30.03.2010 10:54   start
30.03.2010 11:01   end
30.03.2010 11:02   end
31.03.2010 08:33   start
31.03.2010 09:43   end
31.03.2010 15:10   start
31.03.2010 15:34   end

[s.h.a.r.k]

@Blup: Das ist so ziemlich meine Lösung. Allerdings hängt dies davon ab, wie die Frage zu verstehen ist.

[Hubi89]

Wenn ich mir die beiden obigen Lösungen so anschaue, frage ich mich, ob ich die ursprüngliche Frage falsch verstanden habe. Ist die Maximale Zeitdauer einer Überschneidung gefragt oder die maximale Anzahl gleichzeitig laufender Tätigkeiten (maximale Überschneidungen gleichzeitig)?

Edit: Also wenn ich mir die Fragestellung nochmal so anschaue, scheint es zweiteres zu sein, in dem Fall ist mein Algo von oben natürlich nicht zu gebrauchen...

[s.h.a.r.k]

Hier mal meine Idee als Algo, nur noch ein wenig optimiert:

Delphi-Quellcode:

type
  TTimePeriod = record
    StartTimestamp : TDateTime;
    EndTimestamp : TDateTime;
  end;

  TTimePeriodArray = array of TTimePeriod;


function GetMaxTimeOverlaps(const ATimePeriods : TTimePeriodArray): Integer;
var
  TimeArray : array [0..1439] of Integer;
  tp : TTimePeriod;
  i : Integer;
  n : Integer;
  IndexStart, IndexEnd : Integer;
  Maximum, Value: Integer;
begin
  // Verteilung der Zeiten auf das Array
  Maximum := 1;
  for i := 0 to Length(ATimePeriods) - 1 do
  begin
    tp := ATimePeriods[i];

    IndexStart := HourOf(tp.StartTimestamp) * 60 + MinuteOf(tp.StartTimestamp);
    IndexEnd := HourOf(tp.EndTimestamp) * 60 + MinuteOf(tp.EndTimestamp);

    for n := IndexStart to IndexEnd do
    begin
      Value := TimeArray[n];
      Inc(Value);
      if (Value > Maximum) then
        Maximum := Value;
      TimeArray[n] := Value;
    end;
  end;
  Result := Maximum - 1;
end;

[Hubi89]

Sehr ordentlich, damit sollte das Problem wohl gelöst sein.

[msickel]

Zitat von Codewalker:

Muss du das nur einmalig machen? Und brauchst du es in Delphi oder reicht das Ergebnis? In letzterem Fall würde ich vermutlich Excel bemühen, da dürfte das in weniger als 10 Minuten erledigt sein.

brauchen werde ich das wohl jeden Monat, aber die Excel Variante wäre auch sehr interessant.

Gruss Martin