Minimalna liczba usunięć bez nakładania

Mamy nakładające się przedziały i chcemy usunąć jak najmniej przedziałów, aby żadne z nich już się nie nakładały. Należy zachować ich jak najwięcej. ✂️

Usunięcie jak najmniejszej liczby przedziałów jest równoważne zachowaniu jak największej liczby nienakładających się przedziałów. Należy rozwiązać wariant z zachowywaniem, a następnie odjąć liczbę zachowanych przedziałów od n.

Zachowanie jak największej liczby nienakładających się przedziałów to w istocie klasyczny problem wyboru aktywności. Ten sam pomysł zachłanny rozwiązuje oba problemy.

W tym przypadku właściwą kolejnością jest kolejność według czasu zakończenia, a nie rozpoczęcia. Wczesne zakończenie najszybciej zwalnia oś czasu dla kolejnego przedziału, który można zachować.

Należy zawsze zachować spośród nadal zgodnych przedziałów ten, który kończy się najwcześniej. Pozostawia on najwięcej miejsca na pozostałe przedziały.

Należy przechowywać koniec ostatniego zachowanego przedziału. Kolejny przedział jest zgodny tylko wtedy, gdy jego początek znajduje się na tej granicy lub za nią.

Gdy przedział zaczyna się przed last_end, koliduje z poprzednim, więc należy go odrzucić i zwiększyć licznik usunięć o jeden. W przeciwnym razie należy go zachować.

Dowodzi tego argument wymiany: zastąpienie dowolnego zachowanego przedziału zgodnym przedziałem kończącym się najwcześniej nigdy nie zmniejsza liczby przedziałów, które można zachować.

Należy zdecydować, czy [1, 2] i [2, 3] uznaje się za nakładające się. Jeśli wspólny punkt końcowy jest dozwolony, należy użyć testu start >= last_end.

Należy posortować przedziały według końca, wykonać jedno przejście i zliczyć konflikty. Całkowity koszt wynosi O(n log n) z powodu sortowania oraz pojedynczego liniowego przejścia.

Ten schemat pozwala zaplanować najwięcej spotkań w jednej sali albo umieścić najwięcej zadań na jednej maszynie. Warto go rozpoznać zawsze, gdy konflikty trzeba zminimalizować.

Zachłannie zachowywane są nienakładające się przedziały.

Minimalna liczba usunięć jest równa n pomniejszonemu o największą liczbę przedziałów, które można zachować. Należy posortować przedziały według końca, zachłannie zachowywać zgodne przedziały kończące się najwcześniej i zliczyć pozostałe. 🚀