Algorithmus zur Überprüfung der Überlappung zwischen Arrays

Question

Ich habe zwei Arrays, eines der bestehenden Termine und eines der möglichen Termine. Die Arrays enthalten jeweils Werte von/bis zu bestehenden oder potenziellen Terminen. Die Termine in jedem Array sind bereits nach der Uhrzeit sortiert.

Ich muss jeden der potenziellen Termine für jeden der bestehenden Termine überprüfen, um zu sehen, dass es keine Überschneidungen gibt. Ich weiß, dass ich jedes Mal von Anfang an mit den bestehenden Terminen beginnen kann, aber ich suche nach einem effizienteren Weg.

Answer 1

Die Idee: Beginnen Sie, die ersten Intervalle miteinander zu vergleichen. Wenn ein Intervall vollständig vor dem anderen liegt, sehen Sie sich das nächste Intervall an, bis Sie ein überlappendes oder kommendes Intervall gefunden haben. Entweder kommt Intervall A vollständig vor Intervall B, oder B kommt komplett vor A, oder sie überlappen sich irgendwie. Sobald Sie eine Überlappung gefunden haben, können Sie aufhören zu suchen. Dies kann gemacht werden, um das früheste überlappende Paar einfach zurückzugeben, aber das Zurückgeben aller überlappenden Paare würde mehr Arbeit erfordern.

Pseudocode:

Overlaps(actual[1..n], pending[1..m]) 
    i = 1 
    j = 1 
    while i <= n and j <= m do 
     if actual[i].stop <= pending[j].start then 
      i = i + 1 
     else if actual[i].start >= pending[j].stop then 
      j = j + 1 
     else 
      return true 
    return false 

Hinweis - wenn Sie alle überlappenden Paare finden wollen, anstatt nach dem Austritt aus den ersten Überlappungserfassungs, könnten Sie einfach i ausdrucken und j und erhöhen i wenn actual[i].stop <= pending[j].stop oder erhöhen j wenn actual[i].stop > pending[j].stop. Das würde jedes überlappende Paar drucken und ist immer noch lineare Zeit.

Answer 2

Dies kann effizient in O (nlogn) getan werden. Betrachten Sie zwei Arrays A, B, die jeweils vorhandene und potenzielle Termine enthalten. Sortieren A in aufsteigender Reihenfolge der Endzeiten von Terminen (A_end) und Startzeit von Terminen (A_start). Dieser Vorgang dauert O (n log n) Zeit

Für jeden möglichen Termin in B:
s = Punkt der Zuordnung beginnen
t = Endpunkt der Zuweisung

nun binäre Suche auf Array A_start und A_end zu Finden Sie alle Termine, die zwischen der Uhrzeit und der Uhrzeit liegen.
[# Überlappungen =
(Termine mit der Zeit endet < = t) - (Termine mit der Zeit endet < s) +
(Termine mit der Zeit endet> t) - (Termine mit Startzeit> t) +
]

Somit Gesamtauftrag ist O (n log n)

EDIT: #overlaps = sum_1 + SUM_2
Hier sum_1 stellt diese Intervalle mit der Zeit endet < = t. Um aber nur die überlappenden Intervalle zu finden, müssen wir diese Intervalle mit der Endzeit < s subtrahieren. So erhalten wir nur solche mit Endzeit> = s und < = t.
Hier steht sum_2 für jene Intervalle mit der Endzeit> t. Um aber nur die überlappenden Intervalle zu finden, müssen wir diese Intervalle mit der Endzeit> t subtrahieren. So erhalten wir nur solche mit Endzeit> t aber Anfangszeit < = t.

Der Beweis kann durch die Tatsache gegeben werden, dass jedes überlappende Intervall entweder die Endzeit < = t oder> t haben kann.Somit wird es entweder in sum_1 oder sum_2 liegen.

Answer 3

Sie können die Vereinigung der vorhandenen und potenziellen Termine in einem einzigen Array vornehmen und die Union nach Startzeit sortieren. Fügen Sie den Intervallen ein Label hinzu, damit Sie wissen, dass es sich um ein vorhandenes oder ein potenzielles Intervall handelt. (Sie können sie auch in separaten Arrays sortieren und zwei Indizes inkrementieren, aber der Code ist einfacher mit einer Liste).

Sie können dann das kombinierte Array durchlaufen und benachbarte Intervalle zusammenführen, wenn sie sich überlappen. Fassen Sie nur bestehende Termine mit bestehenden und ebenfalls potenziellen Terminen mit Potenzial zusammen. Dazu müssen Sie sich die letzten vorhandenen und möglichen Intervalle merken.

Auf diese Weise müssen Sie nicht bis zum Anfang zurückgehen, Sie müssen nur die zuletzt zusammengeführten Intervalle betrachten.

In psedudocode:

E: existing appointments 
P: potential appointments 

A: union of P and E, sorted by start time 

lastE = [] 
lastP = [] 
for each appointment a in A: 
    if a is existing: 
     if a overlaps with lastE: 
      lastE = lastE + [a] 
     else 
      lastE = [a] 
     if a overlaps with lastP: 
      print all appointments in lastP overlapping with a 
    if a is potential: 
     if a overlaps with lastE: 
      print a 
     if a overlaps with lastP: 
      lastP = lastP + [a] 
     else: 
      lastP = [a] 

Beachten Sie, dass Sie nicht die Struktur lastE speichern müssen, können Sie es als ein einzelnes Intervall definieren und die Start- und Endzeit einzustellen.

Sie müssen jedoch die einzelnen Termine in lastP kennen. Sie können es möglicherweise noch weiter optimieren, indem Sie eine absteigende Reihenfolge nach Endzeit in lastP beibehalten. Dann, in der Zeile, wenn alle Überlappungen zwischen a und lastP gedruckt werden, können Sie aufhören zu suchen, sobald die Endzeit des möglichen Termins in lastP kleiner ist als die Startzeit von a.

Answer 4

Wenn wir zuerst diese beiden Arrays verbinden und die Zeit für die Verbindung ist O (n) und dann sortieren wir das gesamte Array und diese Sortierung benötigt O (nlogn), wenn wir schnelle Sortierung oder merge sort dann verwenden, wenn wir berechnen Gesamtzeitkomplexität, wird es wie dieses

F (n) = O (n) sein, + O (n log n)

so endgültige Komplexität wird O (n log n) sein, den Laser als O (n^2)