0Pricing
Coding Interview Prep · Lekcja

Zamiatanie liniowe dla maksymalnego nakładania

Zliczanie równoczesnych przedziałów za pomocą wydarzeń

Zamiatanie liniowe dla maksymalnego nakładania to bezpłatna lekcja Coding Interview Prep na CoddyKit. To lekcja 3 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.

Pytanie o maksymalne nakładanie

Ile przedziałów obejmuje tę samą chwilę jednocześnie? Największa liczba to maksymalne nakładanie, czyli najbardziej obciążony punkt na osi czasu. 📈

Myślenie zdarzeniami

Proszę przestać myśleć o całych przedziałach. Każdy z nich należy podzielić na dwa zdarzenia: +1 w chwili rozpoczęcia i -1 w chwili zakończenia.

Tworzenie listy zdarzeń

Dla każdego przedziału należy dodać do jednej wspólnej listy zdarzenie rozpoczęcia i zdarzenie zakończenia. Każde zdarzenie zawiera pozycję oraz deltę równą plus jeden lub minus jeden.

events = []
for s, e in intervals:
    events.append((s, 1)); events.append((e, -1))

Sortowanie zdarzeń

Należy posortować każde zdarzenie według pozycji, aby móc przejść przez oś czasu od lewej do prawej i przetwarzać zmiany we właściwej kolejności.

events.sort()

Przejście i zliczanie

Należy przejść po posortowanych zdarzeniach, utrzymując bieżący licznik. Dodając każdą deltę podczas przejścia, otrzymujemy w liczniku liczbę aktualnie aktywnych przedziałów.

active = 0
for pos, delta in events:
    active += delta

Śledzenie maksimum

Po każdej aktualizacji należy porównać licznik z dotychczasowym najlepszym wynikiem. Największa wartość, jaką kiedykolwiek osiągnie licznik, to maksymalne nakładanie.

best = max(best, active)

Sposób rozstrzygania remisów

Przy równych pozycjach kolejność ma znaczenie. Jeśli zakończenie w punkcie x powinno zwolnić miejsce przed rozpoczęciem w punkcie x, należy sortować zakończenia przed rozpoczęciami w tym samym punkcie.

Kodowanie delt do właściwego sortowania

Sprytnym sposobem rozstrzygania remisów jest dobranie delt tak, aby sortowanie krotek zrobiło to automatycznie. Przy jednakowych pozycjach należy umieścić deltę -1 przed deltą +1.

events.append((s, 1)); events.append((e, -1))  # -1 sorts first at a tie

Dlaczego to działa szybko

Tworzy się 2n zdarzeń, sortuje je raz i wykonuje jedno przejście. Cała metoda działa w czasie O(n log n), zdominowanym przez to pojedyncze sortowanie.

Gdzie znajduje zastosowanie

Maksymalne nakładanie pozwala rozwiązywać klasyczne zadania, takie jak wyznaczenie minimalnej liczby sal potrzebnych na spotkania czy maksymalnej liczby jednoczesnych użytkowników serwera.

Nie tylko zliczanie

To samo przejście można łatwo rozszerzyć: śledzić całkowitą długość pokrytego odcinka albo znaleźć każdą pozycję, w której zmienia się liczba aktywnych przedziałów — wszystko w jednym liniowym przejściu.

Szybkie sprawdzenie

Aby znaleźć maksymalne nakładanie, wykonuje się przejście po zdarzeniach.

Podsumowanie

Przedziały należy zamienić na zdarzenia +1 oznaczające rozpoczęcie i -1 oznaczające zakończenie, posortować je, a następnie przejść po nich z licznikiem, aby znaleźć maksimum. Remisy należy rozstrzygać, umieszczając zakończenia przed rozpoczęciami. 🚀

Często zadawane pytania

Czy lekcja „Zamiatanie liniowe dla maksymalnego nakładania” jest bezpłatna?

Tak — pełny tekst „Zamiatanie liniowe dla maksymalnego nakładania” 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 „Zamiatanie liniowe dla maksymalnego nakładania”?

Zliczanie równoczesnych przedziałów za pomocą wydarzeń Ć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 3 z 4.

Ile czasu zajmuje lekcja „Zamiatanie liniowe dla maksymalnego nakładania”?

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