Treffen Sie konfliktalgorithmen
Hatte ich ein interview heute und wurde gebeten, zu prüfen, ob zwei treffen miteinander kollidieren oder nicht. Jedes treffen hat start-und Endzeit.
Ich habe versucht, die Frage zu beantworten, aber nicht, dass bestimmte..kann jemand werfen eine Idee?
bool IsConflict(Datetime s1, Datetime e1, Datetime s2, Datetime e2)
sollte true zurückgeben, wenn der Konflikt da ist, und false, wenn kein Konflikt.
E. g
Wahr, wenn:
(s1, e1)= 8,10
(s2, e2) = 9, 11
(s1, e1)= 7,10
(s2, e2) = 8, 9
(s1, e1)= 8,11
(s2, e2) = 9, 11
und so weiter
- Ich sehe viele sprachspezifische Fragen das wäre hilfreich Antworten, aber nichts Allgemeines...
- Gibt es wirklich nichts mehr, um es, wie es aussieht - nur ein paar
if
s, um zu sehen, ob die Termine sich überschneiden. Dieseif
s könnte gestrafft werden und reduziert in der Anzahl, wenn, zum Beispiel, Daten sortiert werden, in einer bestimmten Weise (zum Beispiel basierend auf Ihren Beginn, und nach auf Ihr Ende). - Dies ist nur eine Variante meiner Antwort hier: stackoverflow.com/questions/143552/comparing-date-ranges/...
- Der interviewer wollte wohl sehen, wie Sie das problem gelöst (ich würde ein Bild malen, wie Lasse hat in seinem verlinkten Antwort)
- Mögliche Duplikate von: stackoverflow.com/questions/4718004/tricky-interview-question
Du musst angemeldet sein, um einen Kommentar abzugeben.
Dies ist die grundlegende Intervall-algebra, siehe meine Antwort hier für mehr details, aber der code würde wie folgt Aussehen:
Gehe ich davon aus, dass sich zwei treffen, wo man anfangen, wo das andere endet nicht in einem Konflikt.
Im einfachen Fall von zwei Intervallen ich denke, das wird funktionieren (ungetestet pseudocode weiter):
Den Sitzungen überlappen, wenn und nur wenn
max(s1, s2) < min(e1, e2)
. Diese Kreuzung basierten Ansatz wird davon ausgegangen, dass die Intervalle(s, e)
offen sind, und setzt (zu Recht oder zu Unrecht), dass ein leer treffens = e
keine überschneidungen mit anderen treffen.Komplexität des folgenden Algorithmus ist O (nlogn)
Der plan
Es sind drei Fälle zu prüfen, mit diesem problem.
(s1 >= s2) && (s1 <= e2)
(e1 >= s2) && (e2 <= e2))
(s1 <= s2) && (e1 >= e2)
So, hier ist die Antwort. Ich entschuldige mich, Es ist nicht die meisten lesbaren Zeilen code.
Den code (pseudo):