Przyporządkowanie Klas do Sal

Witam

mam problem logistyczny ze znalezieniem rozwiązania bardzo proszę o pomoc

a mianowicie mamy 5 klas i 5 sal i chcemy przyporządkować każda klasę danej sali jak takie coś uczynić? rozpisze wizualnie

 |  Klasa 1   |    Klasa 2   |   Klasa 3   |   Klasa 4   |   Klasa 5 

---------------- | ---------------- | ---------------- | ---------------- | ---------------- | ----------------
Sala 1: | x | | x | x |
Sala 2: | x | x | | | x
Sala 3: | | x | x | x | x
Sala 4: | | x | x | x | x
Sala 5: | x | | | | x

na powyższej tablicy jest wypisane jaka klasa ma możliwości

Klasa 1 może odbyć zajęcia w sali 1, 2 i 5
Klasa 2 może odbyć zajęcia w sali 2, 3 i 4
Klasa 3 może odbyć zajęcia w sali 1, 3 i 4
Klasa 4 może odbyć zajęcia w sali 1, 3 i 4
Klasa 5 może odbyć zajęcia w sali 2, 3, 4 i 5

rozwiązanie jest oczywiście takie:

Klasa 1 w sali 1
Klasa 2 w sali 2
Klasa 3 w sali 3
Klasa 4 w sali 4
Klasa 5 w sali 5

zapętlając Klasę wszystko ładnie się wstawi lecz co w takim przypadku:

 |  Klasa 1   |    Klasa 2   |   Klasa 3   |   Klasa 4   |   Klasa 5 

---------------- | ---------------- | ---------------- | ---------------- | ---------------- | ----------------
Sala 1: | x | x | x | x | x
Sala 2: | x | x | | x | x
Sala 3: | x | x | | x | x
Sala 4: | x | x | | x | x
Sala 5: | x | x | | x | x

Klasa 1 zostanie przyporządkowana 1 sali
Klasa 2 zostanie przyporządkowana 2 sali
lecz klasa 3 nie ma już możliwości bo sala 1 jest zajęta przez klasa 1

Tutaj znalazłem rozwiązanie na to lecz dość nieefektywne "Permutajce" po prze-mutowaniu znajdziemy taką kolejność

K3 , K1 , K2 , K4 , K5

wiec algorytm najpierw zacznie wstawiać od Klasy 3 lecz problem tego rozwiązania jest związany z czasem bo o ile przy 5 klasach jest to chwile liczenia przy 15 czas trwania idzie już w setkach godzin.

Może na początku ustawiaj klasy, które mają najmniej wyborów?

tez tak myślałem ale to zda egzamin co najwyżej w przypadku gdy klasa ma jedną możliwość co by ładnie odciążyło permutacje (ale to zakładam że będzie rzadko spotykana sytuacja) bo każda Klasa będzie na początku miała wiele możliwości

 |  Klasa 1   |    Klasa 2   |   Klasa 3   |   Klasa 4   |   Klasa 5 

---------------- | ---------------- | ---------------- | ---------------- | ---------------- | ----------------
Sala 1: | | | | | x
Sala 2: | | | | x | x
Sala 3: | x | | x | x |
Sala 4: | x | x | x | |
Sala 5: | | x | |

ale faktycznie dawało by to fajne rozwiązania:

Klasa 5 = Sala 1
Klasa 2 = Sala 5

 |  Klasa 1   |    Klasa 3   |   Klasa 4 

---------------- | ---------------- | ---------------- | ----------------
Sala 2: | | | x
Sala 3: | x | x | x
Sala 4: | x | x |

dalej upraszczając mamy też jedną możliwość:

Klasa 4 = Sala 2

 |  Klasa 1   |    Klasa 3

---------------- | ---------------- | ----------------
Sala 3: | x | x
Sala 4: | x | x

http://pl.wikipedia.org/wiki/Metoda_węgierska

niestety to raczej nie pomoże w tym bo nie ma tutaj zmiennej jak koszt lub czas a jedynie wartość (jest lub nie ma) czego raczej w macierzach nie da się policzyć

ale mimo wszystko bardzo ciekawy pomysł dziękuję za propozycję

Algorytm węgierski. Tam gdzie nie może odbyć się zajęcie wstawiasz ilość klas plus jeden, tam gdzie może odbyć się wstawiasz 1.

6 | 6 | 6 | 6 | 1
6 | 6 | 6 | 1 | 1
1 | 6 | 1 | 1 | 6
1 | 1 | 1 | 6 | 6
6 | 1 | 6 | 6 | 6

tak?

Może być i tak. Tylko że to nie zgadza się z żadnym z przykładów które podałeś wyżej.