Überprüfen ob es Überschneidungen von Uhrzeiten (vom Typ Calendar) gibt

[fireGlurak]

Hallo,

ich habe 2 Arraylists, welche jeweils Objekte vom Typ Calendar speichert. In der einen Arraylist speicher ich in Anfangszeit und in der anderen Arraylist speicher ich die dazugehörigen Endzeiten (auf dem gleichen Index logischerweise). Nun suche ich nach einer Möglichkeit zu überprüfen ob es Überschneidungen bei den Zeiten gibt. Die Sekunden können ignoriert werden. Für mein Vorhaben reicht es aus zu wissen ob es eine Überschneidung gibt oder nicht. Wo genau es eine Überschneidung gibt ist nicht so wichtig.

Mal ein einfaches Beispiel

listAnfang {10:25, 11:24,13:14}
listEnde{10:55,13:34,17:34}

Somit:
Zeit_1 = 10:25 - 10:55
Zeit_2 = 11:24 - 13:34
Zeit_3 = 13:14 - 17:34

In diesem Fall gibt es Überschneidungen bei Zeit_2 und Zeit_3

algorithmisch müsste ich doch so vorgehen, dass ich jede Zeit mit jeder anderen Zeit vergleichen müsste, oder nicht !? geht es villeicht einfacher/besser ?

 

[httpdigest]

Wenn die Startzeitpunkte aufsteigend sortiert sind, reicht es aus, zu prüfen, ob die Startzeit bei Index `i+1` zeitlich vor (also weiter in der Vergangenheit) der Endzeit bei Index `i` liegt.

 

[fireGlurak]

Wenn die Startzeitpunkte aufsteigend sortiert sind, reicht es aus, zu prüfen, ob die Startzeit bei Index `i+1` zeitlich vor (also weiter in der Vergangenheit) der Endzeit bei Index `i` liegt.

Ah stimmt, das macht es recht einfach! Danke!

 

[Xyz1]

Wenn die Startzeitpunkte aufsteigend sortiert sind, reicht es aus, zu prüfen, ob die Startzeit bei Index `i+1` zeitlich vor (also weiter in der Vergangenheit) der Endzeit bei Index `i` liegt.

Vorsichtig mit solchen Aussagen das ist nämlich falsch.
Wenn es aufsteigend sortiert ist reicht es nicht aus nur den unmittelbaren Nachbarn zu vergleichen.
Diese Aufgabenstellung hatte ich im Studium auch mal und sollte es optimieren....

 

[fireGlurak]

Wenn es aufsteigend sortiert ist reicht es nicht aus nur den unmittelbaren Nachbarn zu vergleichen.

Wieso nicht? Hast du ein Beispiel ? Für mich macht es eigentlich Sinn.

 

[kneitzel]

Also Prüfung, ob es eine Überschneidung gibt: da reicht die Kontrolle mit den Nachfolger.
Wenn man alle Überschneidungen haben will, dann muss man bei einer Überschneidung so lange weiter prüfen, bis es keine Überschneidung mehr gibt.

01:00 - 02:00
01:30 - 01:55
01:45 - 02:00

wenn man das als Beispiel nimmt, dann reicht es, den Nachfolger zu prüfen. Hier würde man dann halt den 1. mit dem 2. Datensatz prüfen und dann kann man abbrechen....

Wenn man alle Überschneidungen haben will, dann muss man weiter prüfen. Da darf man also nicht nur den Nachfolger prüfen. So gibt es auch beim 1. und 3. Datensatz eine Überschneidung.

Die Idee mit dem sortieren ist sehr gut. Was mich da nur massiv stört ist, dass die Werte jeweils in einem Array sind. Zusammen hängende Werte sollten zusammen gespeichert werden. Daher hätte ich eine Klasse Intervall oder so gebaut um dann darauf alles zu implementieren ....

 

[thecain]

Vorsichtig mit solchen Aussagen das ist nämlich falsch.
Wenn es aufsteigend sortiert ist reicht es nicht aus nur den unmittelbaren Nachbarn zu vergleichen.
Diese Aufgabenstellung hatte ich im Studium auch mal und sollte es optimieren....

Für den Fall vom TE aber egal. Wenn der unmittelbare Nachbar nicht überschneidet, dann keiner. Das wäre nur wichtig, wenn man alle Überschneidingen finden will.

 

[Xyz1]

Wieso nicht? Hast du ein Beispiel ? Für mich macht es eigentlich Sinn.

Na gut - wenn es nur darum geht ob es IRGENDEINEN Treffer gibt dann funktioniert es. Geht es aber z B um die Anzahl ALLER Treffer genügts nicht.

Von daher muss man mit solchen absolutistischen Aussagen immer etwas aufpassen. Wenn ich z B behaupten würde alle Elefanten sind rosa und fliegen durch die Luft, wäre das Nonsens.

 

[httpdigest]

Von daher muss man mit solchen absolutistischen Aussagen immer etwas aufpassen.

Meine Antwort war eine Antwort auf den explizit vom TE genannten Anwendungsfall, der sehr klar in der Fragestellung genannt war, und keine absolutistische Antwort auf eine Frage, die nie gestellt wurde. Es ging von Anfang an darum, lediglich herauszufinden, ob es irgendeine Überschneidung gibt.

 

[Xyz1]

Noch ein etwas treffenderes Beispiel, zu sagen in 5 Jahren wird Deutschland zu Indien wäre natürlich auch unsinnig denn es gäbe hier bestimmt noch ein paar nicht indische Bürger.

Wenn einer Methode also nur für eine sehr kleine Gruppe an Fällen funktioniert dann wäre eine kleine Randnotiz durchaus angebracht.

 

[httpdigest]

Das ist doch albern jetzt.
Das ist in etwa so, als hätte jemand gefragt: "Wie male ich einen schwarzen, geraden Strich?", dann jemand antwortet "Du nimmst einen schwarzen Stift und ein Lineal." und darauf dann jemand entgegnet: "Vorsicht mit solchen absolutistischen Aussagen! Es reicht eben nicht, nur einen schwarzen Stift zu nehmen, wenn der Strich z.B. orange sein soll. Ausserdem hilft dir ein Lineal nichts, wenn es ein Kreis sein soll. Also Vorsicht mit solchen Aussagen. Oder erwähne wenigstens, dass die Lösung nur für schwarze Striche funktioniert."