Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

We are going to hold a meeting where everybody will speak in clockwise direction around a table. There are n people with n spots. Each person has a position preference (e.g. some want to go first, some last, etc). Everyone is seated randomly and cannot move from their position. How shall we compute the best starting position on the table to satisfy the most people?

I have an O(n^2) solution: See how many people would be satisfied having assumed each of the positions 1..n as start positions; then return the position that gave the maximum value.

share|improve this question
    
NB I will give a generous bounty ASAP if someone solves this –  d'alar'cop Mar 13 at 9:08
    
That's not the way it works. You assign the bounty first, then maybe someone will be attracted to try the problem at all. –  Kilian Foth Mar 13 at 9:12
    
Yes, I know - but I need to wait 2 days before I can do that –  d'alar'cop Mar 13 at 9:12
1  
Are people only satisfied if they speak exactly at the position they wanted to, or would they also be content if they speak near their position (e.g. if someone wants to go first, but has to go second, that would be suboptimal but still better than going last?) –  amon Mar 13 at 9:13
    
@amon They are "satisfied" if and only if they are given their exact preference. 1 space away might as well be n/2 away :) –  d'alar'cop Mar 13 at 9:14

2 Answers 2

up vote 4 down vote accepted

A fairly simple O(n) algorithm exists:

Let pos be an array so that if the person at seat i wants to speak as n-th, we have an entry pos[i] = n. Where the numbering of the seats starts is irrelevant. Both i and n start counting with zero.

The difference i - pos[i] is the seat where the round would have to start for the person at seat i to be satisfied. We count the satisfied persons per start position in a satisfied array. We can then find the maximum of that array, the index of the maximum is the seat where the round should start for maximum satisfaction.

Java example:

int findBestStart(int[] pos) {
    // ask each seat where they'd like to start
    int[] satisfied = new int[pos.length];
    for (int i = 0; i < pos.length; i++) {
        int start = i - pos[i]
        if (start < 0) start += pos.length;
        satisfied[start]++;
    }

    // find where most would like to start
    int bestSeat = -1;
    int bestSatisfied = -1;
    for (int i = 0; i < satisfied.length; i++) {
        if (satisfied[i] > bestSatisfied) {
            bestSeat = i;
            bestSatisfied = satisfied[i];
        }
    }

    return bestSeat;
}
share|improve this answer
    
Thank you, sir. Very nice. I will throw over a bounty in 2 days –  d'alar'cop Mar 13 at 9:32
1  
@d'alar'cop oh, there is no need for a bounty, I have enough rep as it is. –  amon Mar 13 at 9:34
    
Understood. Glad you do it for the love of it. All the best –  d'alar'cop Mar 13 at 9:35
    
I need to verify, but I think this is the same as the O(n^2) algorithm with just one pass. Therefore while the maximum is likely a good approximation, it probably isn't the maximum. –  Neil Mar 13 at 10:03

If each person knows exactly what order he wants to go in and the seating order is constant, then each person knows what starting position he wants the speaking to start at. This way, you can calculate how many people want speaking start at specific points, which is O(n) in complexity if you the preferred position as index into array.

share|improve this answer
    
+1 Thanks! I know you were first... and the answers are equivalent in concept... but amon gave a more formal response with some code. –  d'alar'cop Mar 13 at 9:31
    
+1 This somehow explained it to me better than the answer with the code –  dj18 Mar 13 at 19:14

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.