Menu
There is a round table. And there are n people, some of them are friends with each other. A person sitting on table can interact with the person adjacent to him if he's a friend.
We have to find an algorithm to arrange the n people on table so as to maximize the total interaction.
676
Try to not talk as much. Whether you want to ask someone how they organise their office space or how they make a perfect meringue, try to listen more than you speak. Your own body cues (smiling, nodding, eye contact) can help encourage someone to share their expertise.
This problem can be reduced to the Travelling salesman problem.
Consider each person as a node in a graph. The cost of moving between friends is 0, and between non-friends is 1. The task is now to find a Hamiltonian cycle with the least cost. This is an NP-hard problem.
A greedy algorithm is to place the person with the least friends first, then try to place two of his friends next to him (if he has more than two friends, choose those two friends who themselves have least friends). Keep going in this manner, placing friends next to friends if possible, until everyone is placed. This won't guarantee finding the optimal solution, but it will be very fast to compute.
118
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
