CODEWITHSUNDEEP
algorithmsortinggraph-theory
JAN
JAN

Reputation: 21875

Seating people in an auditorium algorithm - doesn't work so good

Given the following problem : 

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.

I need to write an algorithm where everybody are happy.

I was thinking about topological sort ,where we throw the problem to the field of graph theory: *Run topological sort on graph G=(V,E). *if there's a sort for the problem - return 'yes' ,otherwise return 'no'. The algorithm would work as follows : In each line we place only one participant ,the first line holds the first participant (where he would be the first vertex in the TopSort),the second line holds the second participant and etc. If participant A don't want to sit behind (or at the same line) participant B then we would have a directed edge from A to B ,that states that A sits behind B.

My problem starts when A doesn't want to sit in the same line as B (or behind him) , and B doesn't want to sit behind A (or at the same line) .

I'd appreciate you help, Regards,Ron

Upvotes: 1

Views: 245

Answers (1)

Vlad
Vlad

Reputation: 35594

Obviously, if there is a circular dependency (A wants to sit before B, and B wants to sit before A), the problem has no solution. Topological sort seems to be an adequate approach to your problem.

Upvotes: 2

Related Questions