Een aantal lesgevers \(L_i\), \(i = 1,...,n\), geeft les aan een aantal groepen studenten \(S_j\), \(j = 1,...,k\). Gevraagd wordt om een lesrooster op te stellen dat zo weinig mogelijk lesuren gebruikt, waarbij uiteraard lessen in parallel kunnen worden gegeven, rekening houdend met de volgende beperkingen:

1. Een lesgever kan niet op hetzelfde moment aan twee studentengroepen lesgeven.
2. Een groep studenten kan niet op hetzelfde moment les volgen bij twee lesgevers.

Opgave

Voor de volgende gegevens: \((L_1, S_1)\), \((L_2, S_1)\), \((L_3, S_1)\), \((L_5, S_1)\), \((L_2, S_2)\), \((L_4, S_2)\), \((L_5, S_2)\), \((L_1, S_3)\), \((L_4, S_3)\) is het volgende schema een goed lesrooster:

Ontwerp en implementeer een gretig algoritme voor het opstellen van een correct lesrooster, d.w.z. een lesrooster dat aan beide beperkingen voldoet, met zo weinig mogelijk lesuren.

Opgave

Schrijf een Python-functie plan(lessen: list). Deze functie neemt een lijst van lessen als argument en geeft een lijst van lesuren terug (voorgesteld door een lijst van tuples). Hierbij wordt een les voorgesteld door een tuple(lesgever, studentengroep).

Zoek een tegenvoorbeeld dat aantoont dat dit algoritme niet steeds een optimaal lesrooster oplevert.

Voorbeelden

>>> plan([('L1', 'L2')])
[[('L1', 'L2')]]
>>> plan([('L1', 'S1'), ('L2', 'S1'), ('L3', 'S1'), ('L5', 'S1'), ('L2', 'S2'), ('L4', 'S2'), ('L5', 'S2'), ('L1', 'S3'),('L4', 'S3')])
[[('L2', 'S1'), ('L4', 'S3'), ('L5', 'S2')], ['L5', 'S1'), ('L1', 'S3'), ('L2', 'S2')], [('L3', 'S1'), ('L4', 'S2')], ['L1', 'S1']]