Maksymalna suma przedziałów nie pokrywających się przedziałów na liście interwałów
Ktoś zadał mi to pytanie:
Otrzymasz listę interwałów. Musisz zaprojektować algorytm, aby znaleźć sekwencję nienakładających się interwałów, tak aby suma przedziałów interwałów była maksymalna.
Na przykład:
Jeśli podane interwały są następujące:
["06:00","08:30"],
["09:00","11:00"],
["08:00","09:00"],
["09:00","11:30"],
["10:30","14:00"],
["12:00","14:00"]
Zasięg jest maksymalizowany, gdy trzy interwały
[“06:00”, “08:30”],
[“09:00”, “11:30”],
[“12:00”, “14:00”],
są wybrane.
Dlatego odpowiedź wynosi 420 (minut).