Algorytmy i struktury danych · Middle · Pytanie 20 z 75
Jak scalić nakładające się przedziały, np. [[1,3],[2,6],[8,10]]?
- 1Porównać każdą parę przedziałów i scalić nakładające się
- ✓Poprawna odpowiedź: Posortować po początku i rozszerzać ostatni scalony przedział albo zacząć nowy
- 3Posortować po końcu i usunąć każdy przedział nakładający się na inny
Wyjaśnienie
Po sortowaniu po początku przedział nakłada się na poprzedni dokładnie wtedy, gdy jego początek nie jest za poprzednim końcem. Jedno przejście daje [[1,6],[8,10]]. Łączny koszt to O(n log n) przez sortowanie.