Maximale nicht überlappende Intervalle in einem Intervallbaum

Question

Angesichts einer Liste von Zeitintervallen muss ich die Menge der maximalen nicht überlappenden Intervalle finden.

Zum Beispiel

, wenn wir die folgenden Intervalle:

[0600, 0830], [0800, 0900], [0900, 1100], [0900, 1130], 
[1030, 1400], [1230, 1400] 

Auch ist es gegeben, dass Zeit im Bereich [0000, 2400] sein.

Die maximale Anzahl nicht überlappender Intervalle ist [0600, 0830], [0900, 1130], [1230, 1400].

Ich verstehe, dass die maximale Verpackungsmenge NP-Complete ist. Ich möchte bestätigen, ob mein Problem (mit Intervallen, die nur Start- und Endzeit enthalten) auch NP-Complete ist.

Und wenn ja, gibt es eine Möglichkeit, eine optimale Lösung in exponentieller Zeit zu finden, aber mit intelligenteren Vorverarbeitungs- und Bereinigungsdaten. Oder wenn es einen relativ einfach zu implementierenden Festparameter-Algorithmus gibt. Ich möchte keinen Approximationsalgorithmus wählen.

Answer 1

Dies ist kein NP-vollständiges Problem. Ich kann an einen O(n * log(n)) Algorithmus denken, der dynamische Programmierung verwendet, um dieses Problem zu lösen.

Angenommen, wir haben n Intervalle. Angenommen, der angegebene Bereich ist S (in Ihrem Fall S = [0000, 2400]). Entweder nehmen Sie an, dass alle Intervalle innerhalb von S liegen, oder eliminieren Sie alle Intervalle innerhalb von S in linearer Zeit.

1. Pre-Prozess:

   • sortieren alle Intervalle durch ihre Punkte beginnen. Angenommen, wir erhalten ein Array A[n] von n Intervallen.
     • nimmt Dieser Schritt O(n * log(n)) Zeit
   • Für alle Endpunkte der Intervalle, den Index des kleinsten Punkt finden beginnen, der nach ihm folgt. Angenommen, wir erhalten ein Array Next[n] von n ganzen Zahlen.
     • Wenn ein solcher Punkt beginnt nicht für den Endpunkt des Intervalls i, existieren können wir n-Next[i] zuweisen.
     • Wir können dies in O(n * log(n)) Zeit durch Aufzählung von n Endpunkten aller Intervalle, und verwenden Sie eine binäre Suche, um die Antwort zu finden. Vielleicht gibt es einen linearen Ansatz, um dies zu lösen, aber es spielt keine Rolle, denn der vorherige Schritt dauert bereits O(n * log(n)).

2. DP:

   • Angenommen, die maximale nicht-überlappenden Intervallen im Bereich [A[i].begin, S.end]f[i] ist. Dann ist f[0] die Antwort, die wir wollen.
   • Auch angenommen f[n] = 0;
   • Zustandsübergangsgleichung:
     • f[i] = max{f[i+1], 1 + f[Next[i]]}
   • Es ist ganz offensichtlich, dass der DP Schritt lineare Zeit in Anspruch nehmen.

Die obige Lösung ist die, die ich mit auf den ersten Blick des Problems kommen. Danach, denke ich, auch einen gierigen Ansatz aus, das einfacher ist (aber nicht schneller im Sinne der O-Notation):

(mit der gleichen Notation und Annahmen als DP-Ansatz oben)

1. Vorverarbeitung: Sortieren Sie alle Intervalle nach ihren Ende Punkten. Nehmen wir an, wir erhalten ein Array B[n] von n Intervallen.

2. Greedy:

   int ans = 0, cursor = S.begin; 
   for(int i = 0; i < n; i++){ 
       if(B[i].begin >= cursor){ 
        ans++; 
        cursor = B[i].end; 
       } 
   } 
   

Die beiden oben genannten Lösungen kommen aus meinem Kopf, aber das Problem ist auch als Aktivität Auswahlproblem bezeichnet, die auf Wikipedia http://en.wikipedia.org/wiki/Activity_selection_problem gefunden werden kann.

Auch Einführung in Algorithmen diskutiert dieses Problem in 16.1.