Use a greedy strategy to create a schedule

problem_10_20_a.py

import itertools

s = """18:01 ! 6:042 
18:01 ! 18:03 
8:01 ! 8:02 
6:042 ! 6:046
6:001; 6:002 ! 6:003 
6:004 ! 6:033
18:01 ! 18:02 
6:046 ! 6:840 
6:001 ! 6:034
18:03; 8:02 ! 6:002 
6:001; 6:002 ! 6:004 
6:033 ! 6:857"""

lines = [e.strip().split(" ! ") for e in s.split("\n")]

G = [(a, b) for x, b in lines for a in x.split("; ")]

V = set(e for p in G for e in p)

def find_minimals(G, V):
    return V - set(c for p, c in G)

def greedy_selection(G, V):
    while len(V) > 0:
        minimals = find_minimals(G, V)
        V = V - minimals
        G = [(p, c) for p, c in G if p not in minimals]
        yield minimals

print(list(greedy_selection(G, V)))