Plan zajęć: najwięcej niekolidujących zajęć

Metoda zachłanna - Algorytmy: zakres rozszerzony (Python)

Mamy zajęcia z godzinami rozpoczęcia i zakończenia, a sala jest jedna. Ile zajęć zmieścimy? Zachłannie wybieramy zajęcia, które **kończą się najwcześniej**, potem kolejne, które zaczynają się nie wcześniej niż koniec poprzednich. Dla tego problemu taki wybór zawsze daje najlepszy wynik.

activities = [(9, 11), (10, 12), (11, 13), (8, 9), (12, 14), (13, 15), (9, 10)]
activities.sort(key=lambda a: a[1])
chosen = []
end = 0
for start, finish in activities:
    if start >= end:
        chosen.append((start, finish))
        end = finish
print("wybrane:", chosen)
print("liczba zajęć:", len(chosen))

Ładowanie interaktywnego edytora... Jeśli się nie pojawi, włącz JavaScript.

Wszystkie lekcje kursu Algorytmy: zakres rozszerzony·Zaloguj się, aby zapisać postęp na koncie.