Sortowanie przedziałów według początku
Porządkowanie wydarzeń przed przetwarzaniem
Sortowanie przedziałów według początku to bezpłatna lekcja Competitive Programming Academy na CoddyKit. To lekcja 1 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.
Czym jest przedział
Przedział to po prostu para liczb: początek i koniec, na przykład [2, 5]. Większość zadań dotyczących przedziałów operuje na liście takich par. 📏
Porządek przywraca przejrzystość
Nieuporządkowane przedziały mogą pojawić się w dowolnej kolejności, co utrudnia analizę. Wstępne sortowanie zamienia chaos w przejrzyste przejście od lewej do prawej.
Sortowanie po początku
Domyślnie należy sortować według wartości początku. Wtedy każdy przedział zaczyna się w punkcie nie wcześniejszym niż poprzedni, dzięki czemu można wykonać jedno przejście w przód.
intervals.sort(key=lambda x: x[0])Krotki sortują się naturalnie
Jeśli przedziały są przechowywane jako krotki, Python automatycznie sortuje je według pierwszego elementu, a następnie drugiego. W tym przypadku nie jest potrzebna nawet funkcja key.
intervals = [(3, 7), (1, 4), (2, 5)]
intervals.sort()Dlaczego najpierw początek
Sortowanie według początku pozwala przetwarzać zdarzenia w kolejności czasowej. Następny przedział może rozpocząć się dopiero później, co jest kluczowym niezmiennikiem przejścia.
Równe początki
Gdy dwa przedziały mają ten sam początek, o ich kolejności decyduje drugi klucz. Sortowanie według (start, end) umieszcza najpierw krótsze przedziały, co często pomaga.
intervals.sort(key=lambda x: (x[0], x[1]))Czasami sortowanie po końcu
W niektórych zadaniach, na przykład przy planowaniu maksymalnej liczby wydarzeń, sortuje się zamiast tego według końca. Należy wybrać klucz odpowiadający informacjom potrzebnym podczas przejścia.
intervals.sort(key=lambda x: x[1])Koszt sortowania
Sortowanie wymaga O(n log n) czasu, co jest niewielkim kosztem i zazwyczaj dominuje w tych zadaniach. Następujące po nim przejście ma koszt zaledwie O(n).
Zachowanie dodatkowych danych
Jeśli każdy przedział zawiera identyfikator lub wagę, należy sortować cały rekord, a nie tylko granice. Klucz określa kolejność, a dane pozostają dołączone.
intervals.sort(key=lambda iv: iv[0]) # iv = (start, end, id)Najpierw sortowanie, potem przejście
Niemal każdy algorytm dotyczący przedziałów działa według schematu najpierw sortowanie, potem przejście. Po ustaleniu właściwej kolejności scalanie, zliczanie i planowanie stają się prostymi pętlami.
Prosty model mentalny
Można wyobrazić sobie przedziały jako gości przybywających na przyjęcie. Sortowanie według początku ustawia ich w kolejności przybycia, dzięki czemu można witać ich po kolei.
Szybkie sprawdzenie
Za chwilę połączą Państwo listę przedziałów.
Podsumowanie
Przedział to para określająca początek i koniec, a sortowanie według początku zamienia nieuporządkowaną listę w przejrzyste przejście. Najpierw należy posortować dane, a następnie przetwarzać je w przód w czasie O(n). 🚀
Często zadawane pytania
Czy lekcja „Sortowanie przedziałów według początku” jest bezpłatna?
Tak — pełny tekst „Sortowanie przedziałów według początku” 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 „Sortowanie przedziałów według początku”?
Porządkowanie wydarzeń przed przetwarzaniem Ć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 1 z 4.
Ile czasu zajmuje lekcja „Sortowanie przedziałów według początku”?
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