Учитывая следующую проблему:
we have participants and we want to place them in an auditorium, where
each of the participants has a list of the people that he/she don't
want to sit behind that person , or at the same line of that person .
We do not have any restriction regarding the number of lines in the auditorium ,or the number of seats.
Мне нужно написать алгоритм, где все будут счастливы.
Я думал о топологической сортировке, где мы бросаем задачу в область теории графов:
* Выполнить топологическую сортировку на графе G = (V, E).
* если есть проблема - верните 'да', в противном случае верните 'нет'.
Алгоритм будет работать следующим образом:
В каждой строке мы размещаем только одного участника, первая строка содержит первого участника (где он будет первой вершиной в TopSort), вторая строка содержит второго участника и т. Д.
Если participant A не хочет сидеть позади (или на той же линии) participant B, то у нас будет направленное ребро от A до B, которое означает, что A сидит позади B.
Моя проблема начинается, когда A не хочет сидеть в одной строке с B (или позади него), а B не хочет сидеть позади A (или в той же строке ).
Буду признателен за помощь,
С уважением, Рон