Intervallplanung (nicht typisch): Maximieren der Gesamtlänge für alle geplanten Intervalle

Question

Gegebene Intervalle, z. (1,3) (2,4) (3,6) (4,7), Plan so finden, dass keine Konflikte bestehen, UND die Gesamtlänge der geplanten Intervalle ist maximal.

Ich habe „Intervall Scheduling“ Art von Fragen untersucht, wenn sie über Themen wie Greedy Lösungen & Dynamische Programmierung in school.I wissen sprechen, dass die Lösungen hängen von dem spezifischen Ziel, hängt für die Planung, zum Beispiel: Zeitplan so viele Intervalle wie möglich ==> Gierig.

Aber für diese Frage, ich denke, wir müssen auf rohe Gewalt zurückgreifen (enumerate)? bitte beraten

Answer 1

Ihr vorgeschlagenes Problem kann immer noch in einem gierigen Ansatz gelöst werden. Da Sie das ursprüngliche Intervallplanungsproblem kennen, werde ich die Lösung basierend auf dem vornehmen, was Sie in der Frageanweisung erwähnt haben.

Schritt 1: Sortierintervalle basierend auf der Startzeit.

Schritt 2: Pflegen Sie einen "Spawn" -Pool, der einen 2-Tupel-Heap verwendet, um die Datenstruktur zu pflegen.

Um genauer zu sein, in Schritt 2, nehmen wir an, wir haben N Intervalle I[0] sortiert ... I[N-1], jeder I hat eine start und ein stop Attribute, so I[i].start <= I[i+1].start. Sie haben einen 2-Tupel-Heap, jedes Tupel repräsentiert (T, M). T bedeutet Zeit, den Heap zu verlassen, oder äquivalent die Stoppzeit des Intervalls; M stellt die maximale Stromabdeckung dar, wenn dieses Intervall gewählt wird. Beachten Sie, dass die Reihenfolge des Heaps von T beibehalten wird. Eine Variable ANS wird beibehalten, die die aktuelle maximale Abdeckung beibehält. Somit läuft der Algorithmus wie folgt aus:

ANS <- 0 
HEAP <- [empty] 
for each sorted intervals `I[i]`: 
    while HEAP.empty() == false && HEAP.first_element.T < I[i].start 
     TMP = HEAP.first_element 
     HEAP.pop_first_element 
     if TMP.M > ANS 
      ANS = TMP.M 
    HEAP.insert((I[i].stop, ANS + I[i].stop - I[i].start))