A group of teachers \(L_i\), \(i = 1,...,n\), teach classes to certain groups of students \(S_j\), \(j = 1,...,k\). How do you create a planning with as few periods as possible? Classes can be taught in parallel, but you have to consider the following limitations:

  1. A teacher cannot teach more than one student group at the same time.
  2. A student cannot follow more than one class at the same time.

E.g., given the following information: \((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)\)

the following planning is valid:

Period 1   Period 2   Period 3   Period 4
\((L_2, S_1)\)   \((L_5, S_1)\)   \((L_3, S_1)\)   \((L_1, S_1)\)
\((L_4, S_3)\)   \((L_1, S_3)\)   \((L_4, S_2)\)    
\((L_5, S_2)\)   \((L_2, S_2)\)        


Design and implement a greedy algorithm that creates a valid planning. This means that a planning does not violate any of the 2 limitations, and uses as few periods as possible.

Find a counterexample that proves that this algorithm does not always create an optimal planning.

Assignment

Write a Python-function plan(classes: list). This function requires a list of classes as it’s input argument and returns a list of periods (represented by a list of tuples). A class is represented by a tuple(teacher, student group).

Examples

>>> 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']]