0Pricing
Coding Interview Prep · Lekcja

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 Coding Interview Prep 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 Coding Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Coding Interview Prep 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, e

Typowe 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 Coding Interview Prep, przejdź na CoddyKit PRO. Kurs Coding Interview Prep 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 Coding Interview Prep 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ąć Coding Interview Prep?

Nie wymagamy żadnego doświadczenia. Coding Interview Prep 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 Coding Interview Prep?

Tak. Każda lekcja Coding Interview Prep 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

  1. Sortowanie przedziałów według początku
  2. Scalanie nakładających się przedziałów
  3. Zamiatanie liniowe dla maksymalnego nakładania
  4. Minimalna liczba usunięć bez nakładania
← Powrót do Coding Interview Prep