# efficient algorithm to place people in a specific order

You are preparing a banquet where the guests are government ofﬁcials from many different countries. In order to avoid unnecessary troubles, you are asked to check the list of international conﬂicts in the last ten years. Then, you will assign the guests to two tables, such that in each table, any two guests are not from countries that had conﬂicts in the last ten years.

Provide an efﬁcient algorithm that determines whether it is possible to make such an assignment. If it is possible to do so, the algorithm should return the assignment of these two tables. What is the running time?

so I guess it asks here that a country can have conflicts with multiple countries and any two guests in the same table should not come from countries that had conflicts in the last ten years.

So lets say there are X number of people in the table then X-2 have conflicts with each other?

-
A question like this is better suited on cs.stackexchange.com – Millardo Peacecraft Apr 3 '14 at 20:45
Have you ever heard of a hypergraph and a $k$-coloring of a hypergraph? – Jared Apr 3 '14 at 20:47
Never mind, you don't need a hypergraph, a regular graph would do (the edges would represent conflicts). You then need to find the chromatic number: en.wikipedia.org/wiki/Graph_coloring#Vertex_coloring of the resulting graph where you represent each official with a vertex and each conflict as an edge connecting two vertices (two officials) and the colors represent the different tables. If the chromatic number is $\leq 2$ then it's possible, otherwise it is not. – Jared Apr 3 '14 at 21:01
This particular problem probably can be solved efficiently (because it's attempting to find a $2$-coloring of a graph). However finding the chromatic number of a graph is, I believe, NP-Complete. So if the question was find the minimum number of tables, then you probably couldn't find an efficient algorithm. – Jared Apr 4 '14 at 0:05

The following procedure should do the trick. It returns false if it is not possible to seat people and true otherwise. It also seats people as a side-effect:

While (not all persons seated){
put a standing person p in the queue
level(p)=0
While (queue not empty){
remove person p from the queue
seat p at table (level(p) mod 2) + 1
for all standing people r conflicting with person p{
level(r)=level(p)+1
}
}
}
for all conlicts c {
if people of the conflict seat at the same table{
return false
}
}
return true


If $X$ is number of people and $C$ is number of conflicts, the running time will be $\mathcal{O}(X+C)$.

-