Scalanie nakładających się przedziałów
Łączenie zakresów, które stykają się lub nakładają
Scalanie nakładających się przedziałów to bezpłatna lekcja Competitive Programming Academy na CoddyKit. To lekcja 2 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Competitive Programming Academy, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Competitive Programming Academy zawiera 4 lekcji w sumie.
Cel scalania
Mając wiele przedziałów, należy scalić te, które stykają się lub nakładają, tworząc możliwie najmniejszą liczbę niepokrywających się zakresów. 🧩
Kiedy dwa przedziały się nakładają
Dwa przedziały nakładają się, gdy jeden z nich zaczyna się przed końcem drugiego. Po posortowaniu według początku oznacza to, że następny początek jest nie większy niż bieżący koniec.
Zawsze najpierw sortowanie
Scalanie działa od lewej do prawej tylko wtedy, gdy przedziały są uporządkowane, dlatego należy zacząć od ich posortowania według początku. To podstawa całego przejścia.
intervals.sort(key=lambda x: x[0])Przechowywanie bieżącego zakresu
Należy przejść po posortowanej liście, przechowując jeden bieżący scalony przedział. Każdy nowy przedział albo go rozszerza, albo rozpoczyna nowy zakres.
Rozszerzanie przy nakładaniu
Jeśli następny początek znajduje się wewnątrz bieżącego zakresu, przedziały nakładają się, więc należy rozszerzyć bieżący koniec do większej z dwóch wartości końcowych.
cur_end = max(cur_end, end)Wybór maksymalnego końca
Nowy koniec należy zawsze wyznaczać za pomocą max. Krótki przedział zawarty w długim nie może skrócić zakresu, który został już zbudowany.
Zamknięcie i otwarcie nowego zakresu
Jeśli następny początek znajduje się za bieżącym końcem, występuje przerwa. Należy dodać ukończony zakres do wyniku i rozpocząć nowy bieżący przedział.
result.append([cur_start, cur_end])Nie należy zapominać o ostatnim
Pętla tworzy końcowy zakres, ale go nie dodaje. Po zakończeniu pętli należy dołączyć ten ostatni bieżący przedział, aby nie został utracony.
Styczność oznacza nakładanie się
Proszę zdecydować, czy [1, 3] i [3, 5] powinny zostać scalone. Zwykle tak, dlatego należy użyć start <= cur_end. Proszę przeczytać treść zadania, aby potwierdzić tę regułę brzegową.
Pełne przejście
Jedno przejście po posortowaniu daje wszystkie scalone przedziały, więc cała metoda działa w czasie O(n log n): sortowanie zajmuje czas logarytmiczny, a przejście jest liniowe.
for s, e in intervals[1:]:
if s <= cur_end:
cur_end = max(cur_end, e)
else:
result.append([cur_start, cur_end]); cur_start, cur_end = s, eTypowe zastosowanie
Scalanie przedziałów usprawnia działanie kalendarzy i systemów rezerwacji: po połączeniu zajętych bloków można zobaczyć rzeczywisty wolny czas. Wiele zadań konkursowych ma właśnie taką postać.
Szybkie sprawdzenie
Przedziały są scalane po posortowaniu ich według początku.
Podsumowanie
Należy posortować przedziały według początku, przechowywać bieżący przedział i rozszerzać go za pomocą max w przypadku nakładania się albo dodać go i rozpocząć nowy po napotkaniu przerwy. Proszę pamiętać o dodaniu ostatniego przedziału. 🚀
Często zadawane pytania
Czy lekcja „Scalanie nakładających się przedziałów” jest bezpłatna?
Tak — pełny tekst „Scalanie nakładających się przedziałów” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Competitive Programming Academy, przejdź na CoddyKit PRO. Kurs Competitive Programming Academy zawiera 4 lekcji w sumie.
Co nauczysz się w „Scalanie nakładających się przedziałów”?
Łączenie zakresów, które stykają się lub nakładają Ćwiczysz Competitive Programming Academy z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć Competitive Programming Academy?
Nie wymagamy żadnego doświadczenia. Competitive Programming Academy w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 2 z 4.
Ile czasu zajmuje lekcja „Scalanie nakładających się przedziałów”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji Competitive Programming Academy?
Tak. Każda lekcja Competitive Programming Academy zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Sortowanie przedziałów według początku
- Scalanie nakładających się przedziałów
- Zamiatanie liniowe dla maksymalnego nakładania
- Minimalna liczba usunięć bez nakładania