Najwięcej zajęć w jednej sali

Zachłanne planowanie zajęć i tankowanie na trasie - Informatyka - liceum klasa 3, zakres rozszerzony (Python)

Zajęcia mają godzinę początku i końca, sala mieści jedne naraz. Chcemy zmieścić **jak najwięcej** zajęć. Reguła zachłanna: wybieraj zajęcia, które **kończą się najwcześniej** i nie kolidują z już wybranymi. Zostawia to najwięcej czasu na resztę, dlatego daje najlepszy wynik.

lessons = [(9, 12), (10, 11), (11, 13), (12, 14), (13, 15), (14, 16), (8, 10)]
chosen = []
end = 0
for start, finish in sorted(lessons, key=lambda l: l[1]):
    if start >= end:
        chosen.append((start, finish))
        end = finish
print(chosen, len(chosen))

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

Wszystkie lekcje kursu Informatyka - liceum klasa 3, zakres rozszerzony·Zaloguj się, aby zapisać postęp na koncie.