0 Daumen
301 Aufrufe

Aufgabe:

Sei eine Menge von reellen Intervallen. Für ein Intervall ∈ ist left() die linke und right() die rechte Grenze des Intervalls. Eine Intervall-Abdeckung ist eine Teilmenge ⊆ , so dass jedes Element, welches in irgendeinem Intervall in vorkommt, auch in einem Intervall in vorkommt, d.h. ⋃∈ = ⋃∈ . Ist zum Beispiel = {[0, 10], [2, 3], [9, 11], [1, 4]}, so ist = {[0, 10], [9, 11]} eine Intervall-Abdeckung.

Gesucht ist nun eine Intervall-Abdeckung mit minimaler Anzahl an Intervallen. Konstruieren Sie hierzu einen effizienten Lösungsalgorithmus. Beweisen Sie die Optimalität Ihres Algorithmus und analysieren Sie die Laufzeit.

Avatar von

1 Antwort

+1 Daumen
 
Beste Antwort

Die Intervalle werden nach linker Grenze aufsteigend in eine Liste \(L_\text{links}\) sortiert.

Über \(L_\text{links}\) wird iteriert. Jeder Iterationsschritt besteht aus folgendem.

  1. Die ersten Intervalle von \(L_\text{links}\) mit gleicher linker Grenze werden aus \(L_\text{links}\) entfernt und in einer Liste \(L_\text{rechts}\) gespeichert.
  2. Das Intervall \([a,b]\) aus \(L_\text{rechts}\) mit der größten rechten Grenze wird dem Ergebnis hinzugefügt.
  3. Die Liste \(L_\text{rechts}\) wird geleert.
  4. Die Intervalle mit linker Grenze kleiner oder gleich \(b\) werden aus \(L_\text{links}\) entfernt. Von diesen werden die Intervalle mit rechter Grenze größer als \(b\) in \(L_\text{rechts}\) gespeichert.
  5. Falls \(L_\text{rechts}\) leer ist, dann zurück zu 1. andernfalls zurück zu 2.

Laufzeit ist \(O(n\log n)\) wegen des anfänglichen Sortierens.

Avatar von 5,6 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community