Gesucht ist eine Intervall-Abdeckung mit minimaler Anzahl an Intervallen. Effizienten Lösungsalgorithmus konstruieren.

Question

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.

Answer 1

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.