Maksymalne niepokrywające się interwały w drzewie interwałowym

Question

Biorąc pod uwagę listę przedziałów czasu, muszę znaleźć zbiór maksymalnych nie nakładających się przedziałów.

Na przykład

jeśli mamy następujące przedziały:

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

Także to jest podane, że czas musi być w przedziale [0000, 2400].

Maksymalny niepokrywający się zestaw przedziałów to [0600, 0830], [0900, 1130], [1230, 1400].

Rozumiem, że maksymalne opakowanie zestawu to NP-Complete. Chcę potwierdzić, czy mój problem (z interwałami zawierającymi tylko czas rozpoczęcia i zakończenia) jest również NP-Complete.

A jeśli tak, to czy istnieje sposób na znalezienie optymalnego rozwiązania w czasie wykładniczym, ale z bardziej inteligentnym przetwarzaniem wstępnym i danymi przycinania. Lub, jeśli istnieje względnie łatwy do wdrożenia algorytm traktowalny z ustalonym parametrem. Nie chcę iść na algorytm aproksymacyjny.

Answer 1

To nie jest problem związany z NP-Complete. Mogę wymyślić algorytm O(n * log(n)) za pomocą programowania dynamicznego, aby rozwiązać ten problem.

Załóżmy, że mamy n interwałów. Załóżmy, że podany zakres to S (w twoim przypadku, S = [0000, 2400]). Przypuśćmy, że wszystkie interwały mieszczą się w zakresie S lub eliminują wszystkie interwały nie mieszczące się w zakresie S w czasie liniowym.

1. Pre-process:

   • Sortuj wszystkie przedziały według ich rozpoczynających punktów. Przypuśćmy, że otrzymamy tablicę A[n] z n przedziałów.
     • Ten etap trwa O(n * log(n)) czas
   • Dla wszystkich punktów końcowych odstępach czasu, znaleźć indeks najmniejszy rozpocząć punkt, który następuje po niej. Załóżmy, że otrzymujemy tablicę Next[n] z liczb całkowitych n.
     • Jeśli taki rozpocząć punkt nie istnieje dla punktu końcowego interwału i, możemy przypisać n do Next[i].
     • Możemy to zrobić w O(n * log(n)) czasie, wyliczając n punktów końcowych wszystkich interwałów i użyć wyszukiwania binarnego, aby znaleźć odpowiedź. Być może istnieje liniowe podejście do rozwiązania tego problemu, ale nie ma to znaczenia, ponieważ poprzedni krok już zajmuje O(n * log(n)) czas.

2. DP:

   • Załóżmy, że maksymalne nie zachodzące na siebie okresy w zakresie [A[i].begin, S.end] jest f[i]. W takim razie potrzebujemy odpowiedzi na pytanie: f[0].
   • Załóżmy także, że f[n] = 0;
   • równanie przejście Stan:
     • f[i] = max{f[i+1], 1 + f[Next[i]]}
   • Jest oczywiste, że etap DP czasu, liniowej.

Powyższe rozwiązanie jest jeden wymyślić na pierwszy rzut oka problemu. Po tym, ja również uważam się chciwy podejście, które jest prostsze (ale nie szybciej w sensie asymptotyczne tempo wzrostu):

(o tej samej notacji i założeń, jak podejście DP powyżej)

1. Przetwarzanie wstępne: Sortuj wszystkie przedziały według ich punktów końcowych punktów. Załóżmy, że otrzymujemy tablicę B[n] z przedziałów n.

2. Chciwy:

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

Powyższe dwa roztwory wyjdzie z mojego umysłu, ale problem jest również określana jako wybór problemu działalności, które można znaleźć na Wikipedii http://en.wikipedia.org/wiki/Activity_selection_problem.

Również, Wprowadzenie do algorytmów omawia ten problem dogłębnie w 16.1.