FInd überlappende Termine in O (n) Zeit?

Ich wurde kürzlich gefragt, ob diese Frage in einem interview. Obwohl ich war in der Lage, die O(n2) - Lösung, der interviewer war besessen von einer O(n) Lösung. Ich habe auch geprüft paar andere Lösungen O(n logn), das habe ich verstanden, aber O(n) Lösung ist noch nicht meine Tasse Tee, die davon ausgeht Termine, sortiert nach der start-Zeit.

Kann das jemand erklären?

Anweisung Problem:die Sie gegeben sind n Termine. Jeder Termin enthält eine Startzeit und eine Endzeit ein. Sie müssen retun alle in Konflikt stehende Termine effizient.

Person: 1,2, 3, 4, 5

App Starten: 2, 4, 29, 10, 22

App Ende: 5, 7, 34, 11, 36

Antwort: 2x1 5x3

O(n logn) Algorithmus: separates start-und end-Punkt wie diesem:

2s, 4s, 29s, 10s, 22s, 5e, 7e, 34e, 11e, 36e

dann Sortieren Sie alle diese Punkte (für Einfachheit nehmen wir an, jeder Punkt ist einzigartig):

2s, 4s, 5e, 7e, 10s, 11e, 22s, 29s, 34e, 36e

wenn wir mal in Folge startet ohne enden, dann ist es überlappend:
2s, 4s benachbart sind, so dass überschneidungen gibt es

Halten wir eine Anzahl von "s" und jedes mal, wenn wir uns begegnen wird es +1, und wenn e angetroffen wird, verringern wir die Anzahl von 1.

InformationsquelleAutor der Frage Dude | 2012-09-05

  1. 16

    Die Allgemeine Lösung für dieses problem ist nicht möglich in O(n).

    Zumindest müssen Sie Sie Sortieren durch die Ernennung start-Zeit, die erfordert O(n log n).

    Es ist ein O(n) Lösung wenn die Liste bereits sortiert. Der Algorithmus beinhaltet im wesentlichen die überprüfung, ob der nächste Termin überlappt wird, indem alle vorherigen. Es ist ein bisschen Feingefühl, um diese ein, wie Sie tatsächlich benötigen zwei Zeiger in der Liste aus, wie Sie es durchziehen:

    • Der aktuelle Termin wird überprüft
    • Der Termin mit der neuesten end-Zeit bisher begegnet (die möglicherweise nicht die Voranmeldung)

    O(n) - Lösungen für den unsortierten Fall könnte nur existieren, wenn Sie andere Einschränkungenz.B. eine Feste Anzahl von Termin-Zeitfenster. Wenn dies der Fall war, dann können Sie mit HashSets, um zu bestimmen, die Ernennung(en) Abdeckung für jeden timeslot, der Algorithmus etwa wie folgt:

    • Erstellen Sie ein HashSet für jeden Zeitschlitz - O(1) da die Slot-Zahl ist eine Feste Konstante
    • Für jeden Termin, zu speichern Ihre ID-Nummer in HashSets der slot(s), die es umfasst - O(n), da eine Aktualisierung der Konstanten Anzahl der Zeitschlitze ist O(1) für jeden Termin
    • Führen Sie durch die Schlitze, die überprüfung auf überschneidungen - O(1) (oder O(n) wenn Sie möchten, Durchlaufen Sie die überlappenden Terminen zurückzusenden, da die Ergebnisse)

    InformationsquelleAutor der Antwort mikera

  2. 3

    Vorausgesetzt, Sie haben einige Einschränkung auf die start-und Endzeiten, und auf die Auflösung an, mit der Sie die Zeitplanung, es scheint so, als wäre es ziemlich einfach, um jeden Termin in ein bitmap mal es tut/nicht verwenden, dann zählen, Sortieren (aka bucket-sort) auf die in-use-slots. Da beide linear sind, das Ergebnis sollte linear sein (obwohl, wenn ich mir denke, ist richtig, sollte es werden linear auf die Anzahl der Zeit Schlitze, anstatt die Anzahl der Termine).

    Zumindest, wenn ich fragte diese, wie eine interview-Frage, die Hauptsache, ich würde hoffen, für die Kandidaten zu Fragen, über diese Hindernisse (d.h., ob diese Einschränkungen zulässig sind). Angesichts der Grad, zu dem es unrealistisch, Termine für 1000 Jahre von jetzt an, oder planen Sie, um eine Genauigkeit von sogar einer minute (nicht zu vergessen so etwas wie eine Nanosekunde), Sie schlagen mich als vernünftigen Einschränkungen, aber Sie sollten sich Fragen, bevor man annimmt.

    InformationsquelleAutor der Antwort Jerry Coffin

  3. 1

    Einem naiven Ansatz sein könnte, um zu bauen zwei parallele Bäume, bestellte sich von der Anfang-Punkt und bestellten durch den Endpunkt jedes Intervall. Dies ermöglicht verwerfen die Hälfte eines jeden Baumes in O(log n) Zeit, aber die Ergebnisse gemischt werden müssen, erfordern O(n) Zeit. Dies gibt uns die Abfragen in O(n + log n) = O(n).

    InformationsquelleAutor der Antwort Rami Jarrar

  4. 0

    Dies ist die beste, die ich denken kann, in entsetzlichen pseudocode. Ich habe versucht, zur Verringerung des Problems so viel wie möglich. Dies ist nur weniger als^2 (glaub ich).

    Beachten Sie, dass die Ausgabe am Ende nicht zeigen, dass jeder Termin, der einem bestimmten Termin zu einem Konflikt mit den auf diesem Termin die spezifischen line-Ausgang...aber irgendwann ist jeder Konflikt angezeigt wird.

    Beachten Sie auch, dass ich umbenannt, die Termine, die numerisch in der Reihenfolge der Startzeit.

    output would be something like the following:

Appointment 1 conflicts with 2
Appointment 2 conflicts with
Appointment 3 conflicts with
Appointment 4 conflicts with 5
Appointment 5 conflicts with


    appt{1},appt{2},appt{3} ,appt{4} ,appt{5}
  2      4       10       22      29
  5      7       11       36      34

    pseudocode

    list=(1,2,3,4,5)
for (i=1,i<=5,i++)
    list.shift()   **removes first element
    appt{i}.conflictswith()=list

for (i=1,i<=n,i++)
{   number=n
    done=false
    while(done=false)
        {if (number>i)
            {if (appt(i).endtime() < appt(number).startime())
                {appt{i}.conflictswith().pop()}
             else
                {done=true}
             number--
             }
        else
            {done=true}
        }
}
for (i=1,i<=n,i++)
    print "Appointment ",i," conflicts with:",appt{i}.conflictswith()

    InformationsquelleAutor der Antwort protist

  5. 0

    Stieß ich auf eine Daten-Struktur namens-Intervall-Baum, mit dessen Hilfe wir finden Intervallen in weniger als O(n log (n)) Zeit, je nach der zur Verfügung gestellten Daten

    InformationsquelleAutor der Antwort Dude

Schreibe einen Kommentar