Activity Selection Problem
Aktywność i trwa od czasu start[i] do czasu finish[i]. Jedna osoba wykonuje jedną aktywność naraz, a następna aktywność musi rozpocząć się ściśle po zakończeniu poprzedniej: aktywność, która rozpoczyna się dokładnie w chwili zakończenia innej, nie może być wykonana jako następna.
Zwróć największą liczbę aktywności, które może wykonać jedna osoba.
Funkcja
- startinteger-array
- godzina rozpoczęcia każdej aktywności
- finishinteger-array
- czas zakończenia każdej aktywności; finish[i] należy do start[i]
- Zwracainteger
- najwięcej aktywności, które jedna osoba może wykonać jedna po drugiej
Ograniczenia
1 ≤ start.length == finish.length ≤ 50000 ≤ start[i] ≤ finish[i] ≤ 105- Aktywność może rozpocząć się i zakończyć w tym samym czasie. Tablice nie są posortowane.
Przykłady
- Wejście
- start = [10, 12, 20, 14, 25, 21]finish = [13, 16, 24, 19, 30, 22]
- Wyjście
- 4
- Wyjaśnienie
- Wykonanie zadań od 10 do 13, od 14 do 19, od 21 do 22 i od 25 do 30 daje 4. Pięć jest niemożliwe: zakres od 10 do 13 koliduje z zakresem od 12 do 16, a zakres od 21 do 22 z zakresem od 20 do 24.
- Wejście
- start = [1, 5, 9]finish = [5, 9, 12]
- Wyjście
- 2
- Wyjaśnienie
- Aktywność od 5 do 9 rozpoczyna się dokładnie w chwili zakończenia pierwszej, więc nie może nastąpić po niej. Wykonanie aktywności od 1 do 5, a następnie od 9 do 12 działa, więc odpowiedź to
2.
- Wejście
- start = [0, 2, 5, 8]finish = [100, 4, 7, 10]
- Wyjście
- 3
- Wyjaśnienie
- Aktywność od 0 do 100 pokrywa się ze wszystkimi pozostałymi. Pomijając ją, 2 do 4, 5 do 7 i 8 do 10 pasują jedna po drugiej:
3.
Pytanie dodatkowe
Dwie osoby pracują teraz równolegle, wykonując każda po jednej czynności naraz. Ile czynności mogą wykonać razem i kto powinien zająć się każdą z nich?
Podpowiedzi
Otwieraj je po kolei. Każda zdradza trochę więcej.
Załóżmy, że już wiesz, którą aktywność wykonasz jako pierwszą. Którą chcesz wybrać, aby później zostało jak najwięcej czasu?
Aktywność, która kończy się najwcześniej, jest zawsze bezpiecznym pierwszym wyborem: plan rozpoczynający się od dowolnej innej aktywności może zamienić ją na tę kończącą się najwcześniej i zachować tę samą liczbę aktywności. Potem to samo pytanie powraca w odniesieniu do aktywności, które zaczynają się po jej zakończeniu.
Posortuj aktywności według czasu zakończenia, przesuwając każdy czas rozpoczęcia razem z czasem zakończenia. Przejdź przez posortowaną listę, pamiętając czas zakończenia ostatniej wybranej aktywności, i wybierz każdą aktywność, której czas rozpoczęcia jest ściśle późniejszy niż ten czas.
Rozwiązanie
Sprawdzanie każdego podzbioru aktywności wymaga czasu wykładniczego. Zamiast tego odpowiedź daje jedna zachłanna zasada: spośród aktywności, które nadal pasują, zawsze wybieraj tę, która kończy się jako pierwsza. Posortowanie według czasu zakończenia pozwala zastosować tę zasadę w jednym przebiegu.
Wybieraj najwcześniejsze zakończenie, raz za razem
Poprawne, ale nie kończy się na największych testach
Intuicja
Aktywność, która kończy się najwcześniej ze wszystkich, jest co najmniej tak dobrym pierwszym wyborem jak każda inna. Nie zwalnia cię później, więc po niej może nastąpić wszystko, co mogłoby nastąpić po dowolnym innym pierwszym wyborze, a zamiana jej na ten wybór pozwala zachować tę samą liczbę aktywności. Po tym wyborze problem powtarza się dla aktywności rozpoczynających się po jej zakończeniu.
W pierwszym przykładzie wybierasz aktywność od 10 do 13, potem od 14 do 19, następnie od 21 do 22, a na końcu od 25 do 30: cztery.
Przy każdym wyborze sprawdzane jest wszystkie n aktywności, więc koszt wynosi n razy tyle, ile wynosi odpowiedź. Gdy wszystkie 5000 aktywności następują jedna po drugiej, daje to 25 milionów sprawdzeń.
Algorytm
- Ustaw
count = 0ilastFinish = -1, poniżej każdego elementu start. - Przeskanuj wszystkie aktywności i znajdź tę, dla której
start[i] > lastFinishi która kończy się najwcześniej. - Jeśli nie ma takiej aktywności, zwróć
count. - W przeciwnym razie zwiększ
counto 1, ustawlastFinishna czas zakończenia tej aktywności i ponownie przeskanuj.
def maxActivities(start, finish):
n = len(start)
count = 0
last_finish = -1 # nothing taken yet; every start is at least 0
while True:
# among the activities that start after last_finish, find the one that ends first
pick = -1
for i in range(n):
if start[i] > last_finish and (pick == -1 or finish[i] < finish[pick]):
pick = i
if pick == -1:
return count
count += 1
last_finish = finish[pick]Sortuj według czasu ukończenia i wybieraj zachłannie
Intuicja
Posortuj aktywności według czasu zakończenia, a napotkasz je w kolejności, w jakiej wyszukiwały je powyższe skany. Przejdź posortowaną listę, przechowując lastFinish — czas zakończenia ostatniej wybranej aktywności. Aktywność, dla której start[i] > lastFinish, kończy się najwcześniej spośród tych, które nadal pasują, więc ją wybierz. Każda inna koliduje z ostatnim wyborem, więc pominięcie jej nic nie kosztuje.
Po posortowaniu pierwszy przykład wygląda tak: 10–13, 12–16, 14–19, 21–22, 20–24, 25–30. Wybierasz pierwszą, trzecią, czwartą i szóstą aktywność: 12 nie jest później niż 13, a 20 nie jest później niż 22.
Remisy w czasie zakończenia nie wymagają żadnej reguły. Gdy wybierzesz aktywność kończącą się w chwili t, każda inna kończąca się w chwili t zaczyna się w chwili t lub wcześniej, więc zostaje pominięta.
Algorytm
- Posortuj aktywności według
finish, przenosząc każdy start wraz z jego zakończeniem. - Ustaw
count = 0ilastFinish = -1. - Dla każdej aktywności w tej kolejności, jeśli
start[i] > lastFinish, dodaj 1 docounti ustawlastFinish = finish[i]. - Zwróć
count.
def maxActivities(start, finish):
order = sorted(range(len(start)), key=lambda i: finish[i]) # earliest finish first
count = 0
last_finish = -1 # nothing taken yet; every start is at least 0
for i in order:
if start[i] > last_finish:
count += 1
last_finish = finish[i]
return count
Pułapki i przypadki brzegowe
- Sortowanie według czasu rozpoczęcia. W trzecim przykładzie aktywność od 0 do 100 zaczyna się jako pierwsza i blokuje pozostałe trzy.
- Wybieranie najkrótszej aktywności jako pierwszej. W przypadku aktywności od 1 do 5, od 5 do 6 i od 6 do 10 najkrótsza jest aktywność od 5 do 6, która koliduje z obiema pozostałymi; aktywności od 1 do 5 i od 6 do 10 dają wynik 2.
- Porównywanie za pomocą
≥zamiast>. W drugim przykładzie daje to 3 zamiast 2. - Sortowanie samego
finish. Każdy czas rozpoczęcia musi pozostać powiązany ze swoim czasem zakończenia, w przeciwnym razie czasy rozpoczęcia zostaną sparowane z niewłaściwymi aktywnościami. - Ustawienie początkowej wartości
lastFinishna 0. Pojedyncza aktywność od 0 do 1 zostanie wtedy pominięta, ponieważ0 > 0jest fałszem.
Najczęstsze pytania3
Jaka jest złożoność czasowa problemu wyboru aktywności?
Sortowanie według czasu zakończenia kosztuje O(n log n), a późniejsze przejście zachłanne ma złożoność O(n), więc dominuje sortowanie. Jeśli aktywności są już posortowane według czasu zakończenia, samo przejście rozwiązuje problem w czasie O(n) i przy użyciu O(1) dodatkowej pamięci.
Czym jest problem N spotkań w jednym pomieszczeniu?
To ten sam problem przedstawiony na przykładzie spotkań: jeden pokój, N spotkań, a każde spotkanie może rozpocząć się dopiero po zakończeniu poprzedniego. Posortuj spotkania według czasu zakończenia i wybieraj każde, które rozpoczyna się po zakończeniu ostatniego wybranego spotkania. Aby wypisać spotkania, zapisuj indeks każdego wybranego spotkania, a przy jednakowym czasie zakończenia wybieraj spotkanie o mniejszym indeksie.
Czy problem wyboru aktywności jest problemem programowania dynamicznego?
Może tak być, ale nie musi. Tabela aktywności posortowanych według czasu zakończenia, zawierająca dla każdej z nich największą liczbę aktywności kończących się wraz z nią, daje odpowiedź w czasie O(n²). Zachłanny wybór jest zawsze bezpieczny, więc wystarczy jedno przejście. Tabela staje się właściwym narzędziem, gdy aktywności mają przypisane wartości i chcesz zmaksymalizować ich sumę.
Podobne zadania
Zadania oparte na tych samych pomysłach. Rozwiązanie dwóch lub trzech utrwala schemat.
def maxActivities(start, finish):
# Napisz kod tutajTest #1
Test #2
Test #3
Argumenty
start = [10, 12, 20, 14, 25, 21] finish = [13, 16, 24, 19, 30, 22]
Oczekiwany wynik
4