Analiza programu – Problem kinomana

Zacznijmy od ogólnej myśli, a potem rozbierzemy program linijka po linijce. Ten program rozwiązuje klasyczny problem:

„Na festiwalu filmowym jest wiele seansów. Każdy ma godzinę rozpoczęcia i zakończenia. Jak wybrać jak najwięcej filmów tak, żeby się nie nakładały?”

Program:

• ma listę filmów z godzinami rozpoczęcia i zakończenia,
• sortuje je według godziny zakończenia,
• potem chciwie (greedy) wybiera filmy tak, aby były niekolidujące.

---

1. Dane wejściowe – lista filmów

P = [9, 16, 15, 18, 14, 10, 10, 13, 15, 18]   # początek
K = [10, 17, 17, 21, 15, 14, 11, 14, 17, 20]  # koniec
IDEN = ["F0", "F1", "F2", "F3", "F4", "F5", "F6", "F7", "F8", "F9"]
N = len(P)

• P[i] – start filmu
• K[i] – koniec filmu
• IDEN[i] – identyfikator filmu
• N – liczba filmów

Listy są równoległe – film F3 to:

• P[3] = 18 (start)
• K[3] = 21 (koniec)
• IDEN[3] = "F3"

---

2. Funkcja Sortuj – sortowanie po zakończeniu filmu

To klasyczny insertion sort, działający równocześnie na trzech listach.

def Sortuj(koniec, poczatek, iden):
    for i in range(1, N):
        pom_koniec = koniec[i]
        pom_poczatek = poczatek[i]
        pom_iden = iden[i]
        j = i - 1
        while j >= 0 and koniec[j] > pom_koniec:
            koniec[j+1] = koniec[j]
            poczatek[j+1] = poczatek[j]
            iden[j+1] = iden[j]
            j -= 1

        koniec[j+1] = pom_koniec
        poczatek[j+1] = pom_poczatek
        iden[j+1] = pom_iden

Krok po kroku:

• Dla każdego elementu od 1 do N–1 próbujemy wstawić go w posortowaną część listy.
• Zapamiętujemy wstawiany film (pom_koniec, pom_poczatek, pom_iden).
• Przesuwamy w prawo wszystkie filmy, które kończą się później.
• Wstawiamy film na właściwe miejsce.

Efekt: filmy są posortowane rosnąco wg czasu zakończenia (K).

---

3. Funkcja Wypisz – wypisanie jednego filmu

def Wypisz(koniec, poczatek, iden, k):
    print(iden[k], ":", poczatek[k], "-", koniec[k])

Drukuje np.: F3 : 18 - 21

---

4. Funkcja Wybierz – sedno algorytmu greedy

def Wybierz(koniec, poczatek, iden):
    Wypisz(koniec, poczatek, iden, 0)
    koniec_poprzedniego = koniec[0]
    for i in range(1, N):
        if poczatek[i] > koniec_poprzedniego:
            Wypisz(koniec, poczatek, iden, i)
            koniec_poprzedniego = koniec[i]

Działa tak:

1. Wybiera pierwszy film (ten kończący się najwcześniej po sortowaniu).
2. Zapamiętuje, kiedy się kończy.
3. Dla każdego kolejnego filmu sprawdza:

   czy jego początek > koniec poprzedniego filmu?

4. Jeśli tak – film się nie nakłada i można go obejrzeć.

To klasyczny algorytm selekcji aktywności – udowodniono, że wybiera maksymalną możliwą liczbę niekolidujących przedziałów.

---

5. Główna część programu

A) wypisanie oryginalnej listy filmów

print("Harmonogram festiwalu:")
for i in range(0, N):
    Wypisz(K, P, IDEN, i)
print()

B) sortowanie filmów

Sortuj(K, P, IDEN)
print("Filmy po sortowaniu:")
for i in range(0, N):
    Wypisz(K, P, IDEN, i)
print()

C) wybór niekolidujących filmów

print("Wybrane filmy:")
Wybierz(K, P, IDEN)

---

Cały analizowany kod programu

'''
    Ćwiczenie 8
    Zapisz pełen kod źródłowy programu Problem kinomana i uruchom program.
'''

P = [9, 16, 15, 18, 14, 10, 10, 13, 15, 18]
K = [10, 17, 17, 21, 15, 14, 11, 14, 17, 20]
IDEN = ["F0", "F1", "F2", "F3", "F4", "F5", "F6", "F7", "F8", "F9"]
N = len(P)

def Sortuj(koniec, poczatek, iden):
    for i in range(1, N):
        pom_koniec = koniec[i]
        pom_poczatek = poczatek[i]
        pom_iden = iden[i]
        j = i - 1
        while j >= 0 and koniec[j] > pom_koniec:
            koniec[j+1] = koniec[j]
            poczatek[j+1] = poczatek[j]
            iden[j+1] = iden[j]
            j -= 1

        koniec[j+1] = pom_koniec
        poczatek[j+1] = pom_poczatek
        iden[j+1] = pom_iden

def Wypisz(koniec, poczatek, iden, k):
    print(iden[k], ":", poczatek[k], "-", koniec[k])

def Wybierz(koniec, poczatek, iden):
    Wypisz(koniec, poczatek, iden, 0)
    koniec_poprzedniego = koniec[0]
    for i in range(1, N):
        if poczatek[i] > koniec_poprzedniego:
            Wypisz(koniec, poczatek, iden, i)
            koniec_poprzedniego = koniec[i]

print("Harmonogram festiwalu:")
for i in range(0, N):
    Wypisz(K, P, IDEN, i)
print()

Sortuj(K, P, IDEN)
print("Filmy po sortowaniu:")
for i in range(0, N):
    Wypisz(K, P, IDEN, i)
print()

print("Wybrane filmy:")
Wybierz(K, P, IDEN)