efficient algorithm to place people in a specific order

Question

You are preparing a banquet where the guests are government officials from many different countries. In order to avoid unnecessary troubles, you are asked to check the list of international conflicts 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 conflicts in the last ten years.

Provide an efficient 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?

Also what algorithm would I use for this, can someone please help me out.

Answer 1

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{
       add r to the queue
       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)$.