# Find a quarrel-free seating order with a greedy algorithm [duplicate]

I'm revising for an Algorithms exam and looking at a sample question it says :

A group of n teenagers $$t_1, \dots, t_n$$ are to sit in a single row of n chairs watching a particulary boring comedy movie. Some teenagers quarrel with each other all the time. The Problem is to devise a seating arrangement for the group in such a way that teenagers sat next to each other do not quarrel.

Propose a solution to this problem using the Greedy approach. Estimate the complexity of the resulting algorithm.

In lectures for greedy problems we've only covered Knapsack Problems so Next Fit/Best Fit for Bin Packing. I can't seem to understand how these methods have any relevance to coming up with a solution for the question.

Obviously I don't expect anyone to answer this, since I've not even made an attempt. But in honesty I don't know where to start. If you guys could give me some sort of hints or just general advice because I'm pretty stranded at the minute.

• What did you try? Where did you get stuck? Solving this exercise for you isn't going to help a whole lot: we'd prefer to help you understand the topic, so you can answer the next question on your own! Dec 29 '14 at 18:08
• This is all revision over my holidays so obviously I don't want someone to do the exercise for me. I've read all the topics we've covered so far for greedy Kruskals, Prims, Knapsack problems. I just don't seem to understand how any of them have any relevance to the question... @DavidRicherby Dec 29 '14 at 18:17
• Model the situation and abstract the problem. Does it look familiar?
– Raphael
Dec 31 '14 at 12:45
• see cs.stackexchange.com/questions/35806 It was posted later ... chance ... Jan 1 '15 at 14:04