Biorąc pod uwagę listę przedziałów czasu, muszę znaleźć zestaw maksymalnych nienakładających się przedziałów.

Na przykład,

jeśli mamy następujące odstępy:

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

Podano również, że czas musi być w zasięgu[0000, 2400].

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

Rozumiem, że maksymalne pakowanie zestawu jest 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 inteligentniejszym przetwarzaniem danych wstępnych i przycinaniem. Lub jeśli istnieje stosunkowo łatwy do zaimplementowania stały algorytm traktowalny. Nie chcę wybierać algorytmu aproksymacji.