# Informatyka — zadanie 1.1

> Źródło: matura.lol — https://matura.lol/question/maturazai-informatyka-inf-2015-05/zad/1.1
> Wersja Markdown strony zadania (dla asystentów AI). Przy cytowaniu podaj matura.lol i link powyżej.

- arkusz: Informatyka · Matura · maj 2015 (rozszerzona)
- rok: 2015
- poziom: rozszerzona
- typ: open
- punkty: 2
- działy: Programowanie i algorytmika, programowanie

## Treść

Zadanie 1. Problem telewidza
W Problemie telewidza mamy program telewizyjny, zawierający listę filmów emitowanych
w różnych stacjach telewizyjnych jednego dnia. Telewidz zamierza obejrzeć jak najwięcej
filmów w całości. Jedyne ograniczenie jest takie, że telewidz może oglądać co najwyżej jeden
film (stację telewizyjną) jednocześnie. Zakładamy, że jednego dnia wszystkie filmy są różne.
Program telewizyjny emisji filmów w 4 stacjach telewizyjnych:
Telewizja / stacja
Film i godziny jego emisji
Czas trwania emisji filmu
TV1
film 1: od 9:00 do 12:00
film 2: od 15:00 do 17:00
3 godziny
2 godziny
TV2
film 3: od 11:00 do 16:00
5 godzin
TV3
film 4: od 12:00 do 14:00
2 godziny
TV4
film 5: od 11:30 do 12:30
1 godzina
Dla programu podanego powyżej telewidz jest w stanie obejrzeć aż trzy filmy, np.: film 1,
film 4, film 2. Przyjmujemy, że telewidz nie traci w ogóle czasu na przełączanie
pomiędzy stacjami (np. o godz. 12:00 z TV1 na TV3). Innymi słowy, czasy emisji filmów 1
i 4 nie kolidują ze sobą.
Rozważ następujący algorytm wyboru filmów do obejrzenia przez telewidza, w którym
w kroku 2. stosuje się jedną z czterech strategii opisanych w tabeli 1.
Specyfikacja:
Dane:
T - zbiór filmów z programu telewizyjnego z godzinami emisji i czasami ich
trwania,
S - strategia z tabeli 1.
Wynik:
P - zbiór filmów, które obejrzy telewidz.
Algorytm:
Krok 1.
Zainicjuj P jako zbiór pusty.
Krok 2.
Dopóki T zawiera jakieś filmy, wykonuj:
stosując strategię S, wybierz ze zbioru T film x i usuń go z T
dodaj film x do zbioru P
usuń ze zbioru T wszystkie filmy, których czasy emisji kolidują z czasem
emisji filmu x.
Krok 3.
Zakończ wykonywanie algorytmu i wypisz wszystkie filmy ze zbioru P.
MIN_1R
Tabela 1. Cztery strategie (S) w Problemie telewidza:
Strategia A
Wybierz film, który trwa najdłużej, a jeśli jest takich więcej, to wybierz
z nich ten, który się najwcześniej kończy. Jeśli jest więcej takich filmów,
wybierz dowolny z nich.
Strategia B
Wybierz film, który trwa najkrócej, a jeśli jest takich więcej, to wybierz
z nich ten, który się najwcześniej kończy. Jeśli jest więcej takich filmów,
wybierz dowolny z nich.
Strategia C
Wybierz film, który się najwcześniej zaczyna, a jeśli jest takich więcej,
to wybierz z nich ten, który się najwcześniej kończy. Jeśli jest więcej
takich filmów, wybierz dowolny z nich.
Strategia D
Wybierz film, który się najwcześniej kończy, a jeśli jest takich więcej,
to wybierz z nich ten, który się najpóźniej zaczyna. Jeśli jest więcej
takich filmów, wybierz dowolny z nich.
Przykład:
Dla podanego programu telewizyjnego zastosowanie w kroku 2. strategii A daje wynik
P = {film 3}, czyli telewidz obejrzy tylko jeden film.

## Rozwiązanie — maturazai.pl (AI)

## Poprawna odpowiedź

| Strategia | Zbiór P |
| B (najkrótszy, najwcześniej kończący) | **{film 5, film 2}** |
| C (najwcześniej zaczynający się, najwcześniej kończący) | **{film 1, film 4, film 2}** |
| D (najwcześniej kończący, najpóźniej zaczynający) | **{film 1, film 4, film 2}** |

## Sposób 1 - symulacja krok po kroku

Lista filmów:
- film 1: 9:00-12:00 (3 h)
- film 2: 15:00-17:00 (2 h)
- film 3: 11:00-16:00 (5 h)
- film 4: 12:00-14:00 (2 h)
- film 5: 11:30-12:30 (1 h)

**Strategia B - najkrótszy, w razie remisu najwcześniej kończący**

1. Najkrótszy film: **film 5** (1 h). Dodaj do P. Usuń kolidujące: film 1 (9-12 koliduje z 11:30-12:30), film 3 (11-16), film 4 (12-14 - 12:00 to wciąż w 11:30-12:30? Wg konwencji 12:00 = koniec film 5, ale film 4 zaczyna o 12:00 - KOLIZJA gdy [a,b) lub przy zachodzeniu - przyjmujemy NIE koliduje z film 5 bo 12:00 to brzeg).
- Dokładniej: film 5 trwa do 12:30, film 4 zaczyna o 12:00 → KOLIZJA. Film 4 usunięty.
- Pozostaje: film 2.
2. Film 2 jest najkrótszy spośród pozostałych. Dodaj do P. Brak kolizji.
3. Koniec. **P = {film 5, film 2}** (2 filmy).

**Strategia C - najwcześniej zaczynający się, najwcześniej kończący**

1. Najwcześniej zaczyna film 1 (9:00). Dodaj. Usuń kolidujące: film 3 (11:00 koliduje), film 5 (11:30 koliduje).
- Pozostaje: film 2 (15-17), film 4 (12-14).
2. Z pozostałych najwcześniej zaczyna film 4 (12:00). Dodaj. Brak kolizji z film 2.
3. Pozostaje film 2. Dodaj.
4. **P = {film 1, film 4, film 2}** (3 filmy).

**Strategia D - najwcześniej kończący, w razie remisu najpóźniej zaczynający**

1. Czasy zakończenia: film 1 → 12, film 5 → 12:30, film 4 → 14, film 3 → 16, film 2 → 17.
Najwcześniej kończy film 1 (12:00). Dodaj. Usuń kolidujące: film 3 (11-16 koliduje), film 5 (11:30-12:30 koliduje).
- Pozostaje: film 2, film 4.
2. Najwcześniej kończy film 4 (14:00). Dodaj. Brak kolizji z film 2.
3. Pozostaje film 2. Dodaj.
4. **P = {film 1, film 4, film 2}** (3 filmy).

## Sposób 2 - implementacja Python

```python
filmy = {
'film 1': (9.0, 12.0),
'film 2': (15.0, 17.0),
'film 3': (11.0, 16.0),
'film 4': (12.0, 14.0),
'film 5': (11.5, 12.5),
}

def koliduje(a, b):
s1, e1 = a; s2, e2 = b
return s1 < e2 and s2 < e1

def algorytm(filmy, klucz):
T = dict(filmy)
P = []
while T:
nazwa = min(T, key=lambda x: klucz(x, T[x]))
P.append(nazwa)
wybrany = T.pop(nazwa)
T = {n: t for n, t in T.items() if not koliduje(t, wybrany)}
return P

# Strategia B: najkrótszy, w remisie najwcześniej kończący
klucz_B = lambda n, t: (t[1] - t[0], t[1])
# Strategia C: najwcześniej zaczynający, w remisie najwcześniej kończący
klucz_C = lambda n, t: (t[0], t[1])
# Strategia D: najwcześniej kończący, w remisie najpóźniej zaczynający
klucz_D = lambda n, t: (t[1], -t[0])

print('B:', algorytm(filmy, klucz_B))
print('C:', algorytm(filmy, klucz_C))
print('D:', algorytm(filmy, klucz_D))

Wynik: B = ['film 5', 'film 2'], C = ['film 1', 'film 4', 'film 2'], D = ['film 1', 'film 4', 'film 2'].

## Reference informatyczny - problem wyboru aktywności (greedy)

> Reference - Activity Selection Problem:
> - Klasyczny problem: dany zbiór przedziałów, wybierz **najwięcej niekolidujących**.
> - **Optymalna strategia zachłanna**: sortuj wg czasu zakończenia rosnąco, bierz pierwszy, usuń kolidujące, powtarzaj. To jest strategia D.
> - Złożoność: O(n log n) (sortowanie) + O(n) (wybór).
> - Strategie A, B, C nie są optymalne - łatwo skonstruować kontrprzykład.

## Schemat oceniania CKE

> Klucz CKE (zadanie 1.1, max 2 pkt):
> - **2 pkt** - poprawne odpowiedzi dla trzech strategii
> - **1 pkt** - poprawne odpowiedzi dla dwóch strategii
> - **0 pkt** - niepełna lub błędna albo brak

## Typowe pułapki

- Pomylenie kolizji na brzegach (czy 12:00-14:00 koliduje z 11:00-12:00?) - w klasycznym problemie aktywności **NIE koliduje** gdy się stykają (przedziały półotwarte [a,b)).
- Strategia B - film 5 jest najkrótszy (1 h) i wyklucza film 4, więc wynik tylko 2 filmy.
- Strategia C i D dają ten sam wynik dla tego programu, ale to przypadek - C nie jest optymalna w ogólności.
- Nieusunięcie wszystkich kolidujących po wyborze.

## Złożoność obliczeniowa

- Algorytm greedy: **O(n²)** przy naiwnej implementacji (każdy wybór + usuwanie).
- **O(n log n)** przy sortowaniu i jednym przejściu.

## Linki

- [dane JSON](https://matura.lol/api/question/maturazai-informatyka-inf-2015-05/zad/1.1)
- [otwórz w wyszukiwarce](https://matura.lol/?problem=maturazai-informatyka-inf-2015-05%2Fzad%2F1.1)

## Podobne zadania

- [Zadanie 2](https://matura.lol/question/informatyka-2025-maj-matura-rozszerzona/zad/2) — Zadanie 2. Zapis symboliczny W pliku symbole.txt zapisano 2000 napisów. Każdy z nich jest zapisany w osobnym wierszu i składa się z dokładnie 12 znaków spośród:
- [Zadanie 7](https://matura.lol/question/informatyka-2025-maj-matura-rozszerzona/zad/7) — Zadanie 7. Poszukiwanie wody na Marsie W trzech plikach tekstowych o nazwach laziki.txt, obszary.txt, pomiary.txt zapisano informacje zawierające dane o poszuki
- [Zadanie 3](https://matura.lol/question/informatyka-2023-maj-matura-rozszerzona/zad/3) — Zadanie 3. Liczba Pi Pewien matematyk jest zafascynowany liczbą π ≈ 3,14159265 do tego stopnia, że zapisał jej rozwinięcie dziesiętne z dokładnością do 10 000 c
- [Zadanie 3](https://matura.lol/question/informatyka-2025-maj-matura-rozszerzona/zad/3) — Zadanie 3. Dron Tor lotu pewnego drona składa się z prostych odcinków. Lot rozpoczyna się w punkcie (0, 0), a kończy w punkcie (20000, 0). Dron poza startem i l

_Ostatnia aktualizacja danych: 2026-10-03_