Wybór aktywności według najwcześniejszego zakończenia
Planowanie największej liczby niepokrywających się wydarzeń
Wybór aktywności według najwcześniejszego zakończenia 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.
Problem planowania
Mając wydarzenia z godzinami rozpoczęcia i zakończenia, wybór aktywności polega na znalezieniu największej liczby wydarzeń, w których można uczestniczyć bez nakładania się dwóch z nich. 📅
Nakładanie się oznacza konflikt
Dwie aktywności kolidują, jeśli jedna rozpoczyna się przed zakończeniem drugiej. Z każdej nakładającej się pary można wybrać tylko jedno wydarzenie.
Zwycięska reguła
Klucz zachłanny polega na tym, aby zawsze wybierać spośród dostępnych wydarzeń to, które kończy się najwcześniej. Wczesne zakończenie pozostawia najwięcej miejsca na kolejne wydarzenia.
Sortowanie według czasu zakończenia
Najpierw należy posortować wszystkie aktywności według czasu zakończenia. Następnie najlepszym kolejnym wyborem jest po prostu pierwsza aktywność w tej kolejności, która pasuje.
events.sort(key=lambda e: e[1])Śledzenie ostatniego zakończenia
Należy przechowywać jedną zmienną z czasem zakończenia ostatnio wybranej aktywności. Każde nowe wydarzenie musi rozpocząć się w tej chwili lub później, aby było zgodne z wyborem.
last_end = -1Jedno przejście i wybór
Należy przejść raz po posortowanej liście. Jeśli wydarzenie rozpoczyna się w chwili last_end lub później, należy je wybrać i zaktualizować last_end do czasu jego zakończenia.
for s, f in events:
if s >= last_end:
count += 1
last_end = fDziała w czasie n log n
Koszt stanowi sortowanie o złożoności O(n log n), po którym następuje jedno liniowe przejście. To wystarczająco szybko nawet dla bardzo dużych danych wejściowych w zawodach.
Dlaczego wygrywa najwcześniejsze zakończenie
Najwcześniejsze zakończenie najszybciej zwalnia oś czasu, dlatego nie może zablokować lepszego planu. Zastąpienie nim dowolnego wyboru w optymalnym harmonogramie nie pogarsza rozwiązania.
Najwcześniejsze rozpoczęcie zawodzi
Wybór według najwcześniejszego rozpoczęcia może wskazać jedno długie wydarzenie, które zajmie cały dzień. Sama długość również bywa myląca, dlatego należy kierować się czasem zakończenia.
Obsługa stykających się granic
Należy ustalić, czy wydarzenie kończące się dokładnie wtedy, gdy inne się rozpoczyna, uznaje się za kolizję. Warunek s >= last_end pozwala na wydarzenia następujące bezpośrednio po sobie.
Częsty schemat zadań konkursowych
Ten schemat kryje się za wieloma zadaniami: rezerwacją sal, oglądaniem programów lub uruchamianiem zadań. Gdy zostanie rozpoznany, można zastosować regułę najwcześniejszego zakończenia.
Szybki test
Należy znaleźć maksymalną liczbę niepokrywających się aktywności.
Podsumowanie
Należy posortować aktywności według czasu zakończenia, a następnie wybierać każdą, która rozpoczyna się po zakończeniu ostatniej wybranej. Jedno sortowanie i jedno przejście dają maksymalny zbiór. 🚀
Często zadawane pytania
Czy lekcja „Wybór aktywności według najwcześniejszego zakończenia” jest bezpłatna?
Tak — pełny tekst „Wybór aktywności według najwcześniejszego zakończenia” 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 „Wybór aktywności według najwcześniejszego zakończenia”?
Planowanie największej liczby niepokrywających się wydarzeń Ć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 „Wybór aktywności według najwcześniejszego zakończenia”?
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
- Sposób myślenia zachłannego
- Wybór aktywności według najwcześniejszego zakończenia
- Plecak ułamkowy według ilorazu
- Rozpoznawanie, kiedy zachłanność zawodzi